Menu
Possible Duplicate:
An array of length N can contain values 1,2,3 … N^2. Is it possible to sort in O(n) time?
Given n numbers at the range [0,n^2 -1] how can we sort them in O(n) run time ?
I have a feeling that the solution involves radix sort ,but I'm still missing something.
The n numbers are integers .
Any ideas ?
REMARK: not homework!
Regards
210
Examples of sorting algorithms with O(1) space complexity include: selection sort, insertion sort, shell sort and heapsort.
If you can bound your input in some way with both a lower and upper bound (and maximum precision/value length), then you can use a Radix Sort which is O(n) . Similarly, Bucket Sort can have O(n) complexity in the best case, but degrades to O(n^2) for bad inputs.
We have now introduced several algorithms that can sort n numbers in O(n lg n) time. Merge sort and heapsort achieve this upper bound in the worst case; quicksort achieves it on average.
The actual time will depend on the distribution of data that you have, but I would do the following:
131
I think you're out of luck. Radix sort is O(k*n), where k is number of digits. In your case, k = log(n^2), resulting in O(n*log(n)).
3
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
