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/divyekapoor
http://www.divye.in
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/OCYjpn_zkigJ.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
