If you do not have any constraints regarding memory is there any algorithm to sort a given array with duplicates in O(n) ?
-
2en.wikipedia.org/wiki/Sorting_algorithmlc.– lc.2012-09-03 01:17:18 +00:00Commented Sep 3, 2012 at 1:17
-
1What about Spaghetti-sort? Though it does requires a non-trivial computing device.Switzy– Switzy2012-11-23 07:21:11 +00:00Commented Nov 23, 2012 at 7:21
Add a comment
|
2 Answers
It depends. 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.
In general, however, if you cannot bound your input and need to use a comparison based sort, it can be proven that O(n log n) is optimal.
When sorting fixed precision integers or floating point numbers (normally up to 64-bits), the values are effectively bounded, and radix sort is possible.
Even if the maximum bit-length of the values is bounded, the longer the bit-length, the larger the constant. In effect, if there are n-values to sort, and each value can have a length or precision up to m bits, the algorithmic complexity is O(nm).
2 Comments
ThomasMcLeod
Yes and how do you express m in terms of n? Well m is in O(log n), right? So you cannot really get better than O(n log n) after all.
ronalchn
m is not necessarily in terms of n. I can have 1 million 8-bit integers to sort. It just means that there are repeats.
Yes. If you do not have any limitations regarding space complexity then you can sort the array with o(n) time complexity.
- Suppose you have an array of k (let k =10) elements.
And (Let) your array is : N[2,6,4,4,1,1,9,5,2,2]
Now, as our consideration we do not have any limitations regarding space.
- Assume that we have a two dimensional array (temp_number[i][j]) of size p (theoretically, consider p is infinite) such that on index i contains some flag and index j contains a link list.
Now, Fill the temp_number[ ][ ] such that every element of array N is put in the index of temp_number[ ][ ] and make flag=1 otherwise keep flag=0.
temp_number[0][1] = [1][1->1->null]
temp_number[1][1] = [1][2->2->2->null]
temp_number[2][1] = [0][3->null]
temp_number[3][1] = [1][4->4->null]
temp_number[4][1] = [1][5->null]
temp_number[5][1] = [1][6->null]
temp_number[6][1] = [0][null]
temp_number[7][1] = [0][null]
temp_number[8][1] = [1][9->null] & so on...
- Now, you can get all the elements who have flag=1 in a single loop.
Note, here in this way, we are not doing like
if(number1 > number2) { //sorting logic... }
so, here you can get the complexity 0(n) because only one loop is there.
