You have an array containing only '0's and '1's. Sort this array in minimum time.

It seems easy, sum all the elements in the array and then reset the array with those many '1's in the end and rest '0's in the beginning. Time complexity is also O(n) with constant space. So it seems the best and easy one.

But if you are OK with this, please read the question again - MINIMUM TIME, it doesn't mean the minimum complexity. In the above solutions you are having 2 passes, one for taking sum and another for setting the array.

This can be done in a single pass:

just start two pointers, ptr1 from starting of the array(I should say from -1) and ptr2 from end of the array(I should say from length of the array).

while ptr2>ptr1
increment ptr1
if (array[ptr1] == 0) continue;
else
decrement ptr2 until array[ptr2] == 1;
if(ptr2> ptr1)
swap array[ptr1] with array[ptr2]


C code:
#include <stdio.h>

#define MAXSIZE 100
#define SWAP(a,b) a^=b^=a^=b
void main()
{
int array[MAXSIZE], i, j, len=-1;

printf("Enter array of 0 and 1, enter -1 to discontinue: ");
do{
len++;
scanf("%d",&array[len]);
}while(array[len] != -1);

i= 0;
j = len;

while(j>i){
if(array[i] == 0){
i++;
continue;
}
while(array[--j] == 1);
if(j>i)
SWAP(array[i],array[j]);
}
}

Now the real challenge is to sort an array containing only 0,1,2 in one pass. I am able to do it in less than 2 passes but not in one pass.

Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.