Sunday, June 2, 2013

[Amazon Online test] Sort an array containing 0, 1 & 2

Given that an array consists of only 0s 1s and 2s sort the array in one pass.

Approach: 

Lets view the problem if the constraint of one pass wouldn't have been there
Scan over the array and count the number of 0, 1, and 2.
Now initialise the array with the 0, 1, 2 with the number of elements, the idea is similar to the counting sort.

To solve the above problem in one pass we can use the famous Dutch national flag algorithm.
The basic idea is to traverse over the array and keep track of the current 0s and 2s and the read pointers(initialised with -1, n and 0). Now traverse the array and keep swapping the current element in the respective buckets of interest.




The implementation is given by

void sort(int a[], int n)
{
   int zero = -1;
   int two = n;
   int current = 0;
 
   while(current < two) {
      switch(a[current]) {
         case 0:
           swap(&a[zero++], &a[current++]);
           break;
         case 1:
           current++;
           break;
         case 2:
           swap(&a[current], &a[two--]);
           break;
      }
   }
}

No comments :

Post a Comment