Radix sort can solve the problem in O(N) time. Max. value of input is N^2 so in binary representation, we need d = 2(logN)+1 digits to represent each number. ( It is O(logN) - thats the key) Now group logN bits ( say r = logN ) The maximum value in each group is O( 2^r) This is the base in which we will do radix sort. No of digits in this new base = d/r Max value of each digit in this new base = 2^r Time taken for radix sort: O( No. of digits * ( Time for sorting each digit ) ) Time for sorting N numbers on one digit = O(n+2^r) So total time = O( d/r * (n+2^r) ) By the choice of d and r, we get Time = O(N).
Infact this will work any range polynomial in N. Note that this is just a theoretical analysis and in general Quick sort beats Radix sort in practice because of the hidden constant factors.... On Jun 28, 9:55 pm, L <prnk.bhatna...@gmail.com> wrote: > There is one way in which we can do O(n). > Convert the numbers in base 'n'. [ O(n) ]. > Now, there are 2-digit numbers, each digit ranging from 0 to n-1. > You can call count-sort 2 times (for each digit), so, complexity is O(n > +n) =O(n). > > On Jun 27, 12:22 am, Dan <dant...@aol.com> wrote: > > > Your question is good for a classroom style discussion/debate. > > However, in the real world, there is no simple answer. > > > There are lots of sorting algorithms. Each one has it's pros & cons > > and no single sorting algorithm is "best", especially when not much is > > known about the data to be sorted. In your case.... about all that > > we really know is that there are no negative numbers involved. I > > don't think that helps very much (any?). Then... you need to > > consider the programming language and computer system used for the > > implementation. Yes. They do matter. Sometimes, they matter a > > LOT. Don't assume that an O(x) algorithm is better than an O(y) > > algorithm just because x is less than y. > > > Dan :-) > > > On Jun 26, 12:14 am, ross <jagadish1...@gmail.com> wrote: > > > > Given a sequence of numbers in the range of 1-N^2, what is the most > > > efficient way to sort the numbers (better than NlgN).. > > > Can counting sort be used here? Is an O(N) solution possible.. -- 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.
