For example the array [0,1,0,1,1,0,0,0,1,1] becomes [0,0,0,0,0,1,1,1,1,1]
Let us look at two approaches to solve this problem. The first one is based on bucket sort and the second is more intelligent.
Method#1:
We can take two counts to keep track of the number of 0s and 1s. We iterate through the array two times. In the first iteration we calculate the counts. In the second iteration we fill the array with respective counts. C++ code is given below.
void sort01(int array[], int n)
{
int count0 = 0;
int count1 = 0;
int i;
for( i = 0; i < n; i++ )
{
if( array[i] == 0 )
count0++;
else if( array[i] == 1 )
count1++;
}
int resInd = 0;
for( i = 0; i < count0; i++ )
{
array[resInd++] = 0;
}
for( i = 0; i < count1; i++ )
{
array[resInd++] = 1;
}
}
Method#2:
We start with two indices one pointing to the beginning, another pointing to the end of the array. We increment the begin index until we find a 1. We decrement the end index until we find a 0. We swap these two values so that all 0s move to beginning and all 1s move to the ending.
We repeat these steps until both indices meet. This algorithm goes through the array only once. Look at the following steps in action for the example input.
[0 1 0 1 1 0 0 0 1 1]
L–> <–R
[0 1 0 1 1 0 0 0 1 1] – Swap A[L], A[R]
L R
[0 0 0 1 1 0 0 1 1 1] – “
L R
[0 0 0 0 1 0 1 1 1 1] – “
L R
[0 0 0 0 0 L 1 1 1 1] – “
void sort01(int array[], int n)
{
int low = 0,high = n-1;
while ( low < high )
{
while( low < high && array[low] == 0 )
low++;
while( low < high && array[high] == 1 )
high--;
if( low < high)
swap( array[low], array[high] );
}
}
Even though both algorithms run in O(n) time, the first algorithm traverse through the array two times and the second algorithm traverse through the array only once.