We have an array that contains only 0, 1 and 2. We have to write a program to sort this array.
For example if the input array is [2,0,1,2,1,0,0,2], the output should be
[0,0,0,1,1,2,2,2].
As the first thought, we can very well use well known sorting algorithms like Quick sort, or Merge sort or Heap sort. But that would be an overkill to solve this problem. We can utilize the property that the array contains just 0,1, and 2.
Method#1: Bucket sort approach – Simple
Just take three counters to count 0,1 and 2. Update these while iterating through the array. This is an example of bucket sort with three buckets. Every time we see a 0, we put that in 0th bucket. If we see a 1 we put that into a 1st bucket and so on…
In the second iteration, Fill the array with respective counts of 0,1, and 2 in that order. The following is the Java implementation.
For example if the input array is [2,0,1,2,1,0,0,2], the output should be
[0,0,0,1,1,2,2,2].
As the first thought, we can very well use well known sorting algorithms like Quick sort, or Merge sort or Heap sort. But that would be an overkill to solve this problem. We can utilize the property that the array contains just 0,1, and 2.
Method#1: Bucket sort approach – Simple
Just take three counters to count 0,1 and 2. Update these while iterating through the array. This is an example of bucket sort with three buckets. Every time we see a 0, we put that in 0th bucket. If we see a 1 we put that into a 1st bucket and so on…
In the second iteration, Fill the array with respective counts of 0,1, and 2 in that order. The following is the Java implementation.
public static void sort012(int[] array)
{
int count0 = 0;
int count1 = 0;
int count2 = 0;
int i;
//Count 0's, 1's and 2's
for( i = 0; i < array.length; i++ )
{
switch( array[i] )
{
case 0:
count0++;
break;
case 1:
count1++;
break;
case 2:
count2++;
break;
}
}
//Fill the array with respective counts
int resInd = 0;
for( i = 0; i < count0; i++ )
{
array[resInd++] = 0;
}
for( i = 0; i < count1; i++ )
{
array[resInd++] = 1;
}
for( i = 0; i < count2; i++ )
{
array[resInd++] = 2;
}
}
Method#2: Dutch National Flag
algorithm (Tricky)
This algorithm is based on Dutch national flag problem proposed by famous computer scientist Dijkstra.
In this method the array is divided into three partitions each partition is tracked by three indices. The first part stores 0s, the second part stores 1s and the third part stores 2s.
ind0 , ind1 starts from the beginning of the array, and ind2 starts from the ending of the array.
In each iteration we increment ind1 and examine the element at array[ind1].
- If it is 0 we have to push that left part and increment ind0, and ind1.
- If it is 1 we simply increment ind1.
- If it is 2 we push it to the end and decrement ind2.
- Repeat the above 3 steps until ind1 and ind2 meet each other.
This algorithm scans the array only once.
Here is the snapshot of the array in each iteration.
|
2
|
0
|
1
|
2
|
1
|
0
|
0
|
2
|
|
Ind0, Ind1
|
Ind2
|
|
2
|
0
|
1
|
2
|
1
|
0
|
0
|
2
|
|
Ind0, Ind1
|
Ind2
|
|
0
|
0
|
1
|
2
|
1
|
0
|
2
|
2
|
|
Ind0, Ind1
|
Ind2
|
|
0
|
0
|
1
|
2
|
1
|
0
|
2
|
2
|
|
Ind0, Ind1
|
Ind2
|
|
0
|
0
|
1
|
2
|
1
|
0
|
2
|
2
|
|
Ind0, Ind1
|
Ind2
|
|
0
|
0
|
1
|
2
|
1
|
0
|
2
|
2
|
|
Ind0
|
Ind1
|
Ind2
|
|
0
|
0
|
1
|
0
|
1
|
2
|
2
|
2
|
|
Ind0
|
Ind1
|
Ind2
|
|
0
|
0
|
0
|
1
|
1
|
2
|
2
|
2
|
|
Ind0,
|
Ind1, Ind2
|
public static void sort012(int[] array)
{
int ind0 = 0;
int ind1 = 0;
int ind2 = array.length-1;
while( ind1 <= ind2 )
{
if( array[ind1] == 0 )
{
//swap ind0, ind1 elements
int temp = array[ind0];
array[ind0] = array[ind1];
array[ind1] = temp;
ind0++;
ind1++;
}
else if( array[ind1] == 1 )
{
ind1++;
}
else if( array[ind1] == 2 )
{
//swap ind1, ind2 elements
int temp = array[ind1];
array[ind1] = array[ind2];
array[ind2] = temp;
ind2--;
}
}
}