@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 <[email protected]> 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 [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.
