@Divye: Good theoretical proof and analysis as well.. As you
mentioned, this one works like charm for uniformly distributed
inputs :)
On Jun 26, 8:36 pm, DK <divyekap...@gmail.com> wrote:
> Use a radix sort.
> Complexity of the radix sort is O(N k) where k is the number of digits used
> to represent the number in some base b.
> If we use the convenient fiction that both N and N^2 fit into the same 32
> bit integer then
> k is a constant and we get an O(N) sort. (It's kindof cheating :) ).
> Okay, since we don't want to cheat on this one, keep reading below: :)
>
> Another method is to divide the Numbers into N bins of size N numbers.
> Eg. Bin 1 = 1 to N, Bin 2 = N+1 to 2N ...
> Assuming uniform distribution, the bins will have N/N ~ 1 element each.
> If the distribution is non-uniform then no bin will have more than N
> elements.
>
> For small bins, apply a variant of insertion sort (which performs faster
> than O(n log n) sorts for < 12 elements) and if N is large, will perform
> much faster than counting sort.
> For large bins, apply an O(n log n) sort or radix sort or counting sort.
> (make a choice depending on number of elements in the bin. eg. Num_elements
> ~ N then choose counting sort, else choose radix or O(n log n) sorts)
>
> Complexity analysis:
> 1. No bin will have more than N elements.
> 2. No bin while being sorted will have a range > N.
>
> If the data distribution is uniform, the solution will be very very quick
> (order of N) as the sorting time for bins with just 2 to 3 elements is
> approximately O(num_elements) ~ O(1) and number of such bins is O(N).
> If the data distribution is non-uniform, then complexity will depend on the
> number of bad bins and the size of bad bins.
>
> Let K bins be bad. Here, K is a value dependent on data distribution of the
> input.
> If K is small, number of elements per bin is large -> apply counting sort on
> the bins -> complexity O(K N) which is approximately O(N)
> If K -> log N, apply an O(N log N) sort to the bins -> complexity O( K * N/K
> log (N/K)) -> O(N log (N/log N))
> If K > log N but K < N, worst case -> complexity Sum over K bins{min{O(Ni
> log (Ni)), O(N)}} (you can cheat this to O(N) by using something like radix
> sort)
> If K -> N -> Not possible as you won't have that many bad bins as the number
> of elements per bin will approach 1.
>
> So, in short, you can get a complexity of the kind O(N log (N/log N)) which
> is slightly better than O(N log N).
> Hope this helps!
>
> --
> DK
>
> http://twitter.com/divyekapoorhttp://www.divye.in
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
