CODEWITHSUNDEEP
algorithmsorting
Ziyan Junaideen
Ziyan Junaideen

Reputation: 3310

Sorting Array in O(n) complexity

I was asked an interesting question at my interview at Atrenta. It was to sort an array with an complexity of O(n) which I said is not possible but he insisted it is, even after the interview.

It is like this.

You have an array, lets say : [1,0,1,0,1,1,0] and this needs to be sorted. What ever has to be done within the array (in the sense no other data structure involved.

I haven't and I don't think it is possible to do any sort with an complexity of O(n). The best I could think of is O(n * log n) and my knowledge comes from Wikipedia.

Please give me your ideas and well a way to do it if you know.

Upvotes: 2

Views: 7640

Answers (3)

Mehul Sharma
Mehul Sharma

Reputation: 1

Since it is a binary array, It is possible to solve it with complexity of O(n) using the two pointer method. The code will look like this :

void sort01(int arr[], int n){
int i = 0, j = n - 1;
while (i <= j){
    if (arr[i] == 0)
    {
        i++;
    }
    else
    {
        swap(arr[i], arr[j]);
        j--;
    }
  }
}

Upvotes: 0

Dinushan
Dinushan

Reputation: 2077

Traverse the array from both ends and Swap 1's and 0's when needed.Runs in O(n) but has all the if conditions(bruteforce like approach.probably not the expected answer) ;)

int i = 0 ;
int j = array.size -1 ;
for ( i = 0 ; i < j ; ) {

    if( array[i] == 1) {
        if( array[j] == 0 ) {
            array[j] = 1 ; array[i] = 0 ; //Swap 
            i++; j--; 
            continue;
        }
        //else
            j--;
            continue;

    }
   //else
        if( array[j] == 0 ) {
            i++; 
            continue;
        }

        //else 
            i++ ;
            j--;            
}

Upvotes: 2

Steve Jessop
Steve Jessop

Reputation: 279395

In your example there are only two different values in the array, so you could use counting sort:

zero_count = 0
for value in array:
    if value == 0:
        zero_count += 1
for i in 0 ... zero_count:
    array[i] = 0
for i in zero_count ... array.size:
    array[i] = 1

Radix sorts are a family of more generally applicable O(n) sorts.

It is comparison sorts that require Omega(n * log n) comparisons on average and hence cannot run in worst-case or average-case linear time.

Upvotes: 9

Related Questions