-
February 8th, 2011, 08:39 PM
#1
Sorting faster than n log n?
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)?
-
February 8th, 2011, 11:59 PM
#2
Re: Sorting faster than n log n?
If the distribution of the numbers is uniform, then I recommend Counting Sort (linear time sort), you can google it
-
February 9th, 2011, 04:49 AM
#3
Re: Sorting faster than n log n?
Radix Sort can give you run-time complexity of O(n).
Regards,
Zachm
-
February 9th, 2011, 09:07 PM
#4
Re: Sorting faster than n log n?
Originally Posted by Zachm
Radix Sort can give you run-time complexity of O(n).
Regards,
Zachm
How do you obtain O(n) in radix sort?
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?
-
February 9th, 2011, 09:11 PM
#5
Re: Sorting faster than n log n?
Originally Posted by Zachm
Radix Sort can give you run-time complexity of O(n).
Regards,
Zachm
Oh, forgive my earlier post, I did after all say that my numbers were limited by 10 digits hence 10n is O(n) obviously.
But if the maximum number of digits is indeed k, then it is O(kn), right?
-
February 9th, 2011, 11:51 PM
#6
Re: Sorting faster than n log n?
Originally Posted by getpagesize
Oh, forgive my earlier post, I did after all say that my numbers were limited by 10 digits hence 10n is O(n) obviously.
But if the maximum number of digits is indeed k, then it is O(kn), right?
Right.
Regards,
Zachm
-
March 10th, 2011, 01:00 PM
#7
Re: Sorting faster than n log n?
Hello guys, it is very interesting to know that.
One question. Is quick sort better than both radix sort and bucket sort in practical??
-
March 11th, 2011, 03:30 AM
#8
Re: Sorting faster than n log n?
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
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|