Sort an array with 1s and 0s.

Sometimes you may need to sort an array consisting only two numbers. Let say ones and zeros. Here I am going to explain an algorithm, to solve such problem using one traverse, without using an additional array, and what really happen is, that it segregates ones and zeros in the array. You may see that this method is efficient than a usual sorting algorithm.

Let’s take the following array as an example. 

 array = {0, 1, 1, 0, 0, 1, 1} 

Here I use two variables named left and right.

•  left – keep the array index when it is moved from left to right (left++)
•  right - keep the array index when it is moved from right to left (right--)

The variable left increases until array[left] equals to 0 and similarly variable right decreases until array[right] equals to 1. If the left is less than right then 0 and 1 get interchanged and similar process happens until left is less than right.

1. {0, 1, 1, 0, 0, 1, 1}    left = 0, right = 6;
2. {0, 1, 1, 0, 0, 1, 1}    left = 1, right = 6;
3. {0, 1, 1, 0, 0, 1, 1}    left = 1, right = 5;
4. {0, 1, 1, 0, 0, 1, 1}    left = 1, right = 4;
5. {0, 0, 1, 0, 1, 1, 1}    left = 1, right = 4;
6. {0, 0, 1, 0, 1, 1, 1}    left = 2, right = 4;
7. {0, 0, 1, 0, 1, 1, 1}    left = 2, right = 3;
8. {0, 0, 0, 1, 1, 1, 1}    left = 2, right = 3;
9. {0, 0, 0, 1, 1, 1, 1}    left = 3, right = 3;
10. {0, 0, 0, 1, 1, 1, 1}    left = 3, right = 2;

Here is the C implementation of the above algorithm.

void sort_zeros_ones(int array[], int size)
{
  int left = 0, right = size-1;   
  while(left < right)
  {
     while(array[left] == 0 && left < right)
        left++;
     while(array[right] == 1 && left < right)
        right--;
     if(left < right)
     {
       array[left] = 0;
       array[right] = 1;
       left++;
       right--;
     }
  }
}