Printable View
Input is n integers, but we know that they cannot exceed 10 digits, i.e. the largest number is 10^10
How can we take advantage of this to beat O(n log n)? Obviously sheer bucket sort is out of the question with such large numbers, what else can I do to avoid doing a comparison sort such that I can beat O(n log n)?
If the distribution of the numbers is uniform, then I recommend Counting Sort (linear time sort), you can google it
Radix Sort can give you run-time complexity of O(n).
Regards,
Zachm
How do you obtain O(n) in radix sort?Quote:
Originally Posted by Zachm
Bucket sort is O(n), and bucket sort has to be executed at least k times, where k is the maximum number of digits in the array to be sorted, thus radix sort is O(kn), where n is the number of elements in the array to be sorted?
Oh, forgive my earlier post, I did after all say that my numbers were limited by 10 digits hence 10n is O(n) obviously.Quote:
Originally Posted by Zachm
But if the maximum number of digits is indeed k, then it is O(kn), right?
Right.Quote:
Originally Posted by getpagesize
Regards,
Zachm
Hello guys, it is very interesting to know that.
One question. Is quick sort better than both radix sort and bucket sort in practical??
Radix and count sorting unfortunately have hideous memory overheads for such size because they have to build histogram tables often called key or index tables.
Radix sort will give OkN on average
Count sorting will give O(N+k) on average
Quicksort with random pivot selection is usually the safest bet for time, speed and overhead