u can use radix sort On Sun, Jun 26, 2011 at 9:44 PM, ross <[email protected]> wrote:
> @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. > > -- regards Apoorve Mohan -- 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.
