3

If you do not have any constraints regarding memory is there any algorithm to sort a given array with duplicates in O(n) ?

obataku
  • 29,212
  • 3
  • 44
  • 57
RagHaven
  • 4,156
  • 21
  • 72
  • 113

2 Answers2

12

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).

ronalchn
  • 12,225
  • 10
  • 51
  • 61
Yuushi
  • 25,132
  • 7
  • 63
  • 81
  • 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. – ThomasMcLeod Sep 03 '12 at 03:04
  • 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. – ronalchn Sep 03 '12 at 03:09
4

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.

Manan Shah
  • 1,042
  • 2
  • 14
  • 26