We can solve this by many different ways.
Solution 1
Will be counting all the number of 0’s, 1’s and 2’s. Then insert those number of elements in the array. We have discussed this solution in the below link:
Solution 2:
This will be an in place solution.
In this solution, we take 3 variables [n0, n1, n2] and set them to “-1”
We start iterating from first element of the array.
If the element is “0” then increment index of all the 3 variables [n0, n1, n2], and place the appropriate value.
If the element is “1” then increment index of 2 variables [n1, n2], and place the appropriate value.
If the element is “2” then increment index of n2, and place the appropriate value.
Pseudo code:
if (array[i] == 0)
{
array[++n2] = 2; array[++n1] = 1; array[++n0] = 0;
}
else if (array[i] == 1)
{
array[++n2] = 2; array[++n1] = 1;
}
else if (array[i] == 2)
{
array[++n2] = 2;
}let us analyse by taking an example:
2, 0, 2, 1, 1, 0
n0 = -1
n1 = -1
n2 = -1
for i = 0 to 5
a[0] => 2
a[++n2] = a[0] = 2
At the end of the loop, below are the updated values:
n0 = -1
n1 = -1
n2 = 0
array:
2, 0, 2, 1, 1, 0
===================
n0 = -1
n1 = -1
n2 = 0
Input array:
2, 0, 2, 1, 1, 0
for i = 1 to 5
a[1] => 0
a[++n2] = a[1] = 2
a[++n1] = a[0] = 1
a[++n0] = a[0] = 0
At the end of the loop, below are the updated values:
n0 = 0
n1 = 0
n2 = 1
array:
0, 2, 2, 1, 1, 0
===================
n0 = 0
n1 = 0
n2 = 1
Input array:
0, 2, 2, 1, 1, 0
for i = 2 to 5
a[2] => 2
a[++n2] = a[2] = 2
At the end of the loop, below are the updated values:
n0 = 0
n1 = 0
n2 = 2
array:
0, 2, 2, 1, 1, 0
===================
n0 = 0
n1 = 0
n2 = 2
Input array:
0, 2, 2, 1, 1, 0
for i = 3 to 5
a[3] => 1
a[++n2] = a[3] = 2
a[++n1] = a[1] = 1
At the end of the loop, below are the updated values:
n0 = 0
n1 = 1
n2 = 3
array:
0, 1, 2, 2, 1, 0
===================
n0 = 0
n1 = 1
n2 = 3
Input array:
0, 1, 2, 2, 1, 0
for i = 4 to 5
a[4] => 1
a[++n2] = a[4] = 2
a[++n1] = a[2] = 1
At the end of the loop, below are the updated values:
n0 = 0
n1 = 2
n2 = 4
array:
0, 1, 1, 2, 2, 0
===================
n0 = 0
n1 = 2
n2 = 4
Input array:
0, 1, 1, 2, 2, 0
for i = 5 to 5
a[5] => 0
a[++n2] = a[5] = 2
a[++n1] = a[3] = 1
a[++n0] = a[1] = 1
At the end of the loop, below are the updated values:
n0 = 0
n1 = 2
n2 = 4
array:
0, 0, 1, 1, 2, 2
Hence the final result
Solution 3:
Taking 3 pointers
We take 3 pointers low, mid, high. From the input, we know that mid is “1”, and the elements lesser than mid will be swapped to the left of mid, and the elements greater than mid, will be pushed to the right of mid.
The algorithm will look similar as below:
while (mid <= high)
{
if (arr[mid] == 0)
swap(arr[mid++], arr[low++]);
else if (arr[mid] == 1)
mid++;
else
swap(arr[mid], arr[high--]);
}Let us understand with the help of an example:
Input array = 2, 0, 2, 1, 1, 0
low = 0
mid = 0
high = arr.size() – 1 => 5
In the begenning of pass 1 values are:
low = 0 mid = 0 high = 5
Input array = 2 0 2 1 1 0
In the begenning of pass 2 values are:
low = 0 mid = 0 high = 4
Input array = 0 0 2 1 1 2
In the begenning of pass 3 values are:
low = 1 mid = 1 high = 4
Input array = 0 0 2 1 1 2
In the begenning of pass 4 values are:
low = 2 mid = 2 high = 4
Input array = 0 0 2 1 1 2
In the begenning of pass 5 values are:
low = 2 mid = 2 high = 3
Input array = 0 0 1 1 2 2
In the begenning of pass 6 values are:
low = 2 mid = 3 high = 3
Input array = 0 0 1 1 2 2
Thus the result
===================
Solution in C++
/*
* File : sort_colors.cpp
*/
#include<iostream>
#include<vector>
using namespace std;
void sort_colors_in_place(std::vector<int> &matrix)
{
int n0 = -1, n1 = -1, n2 = -1;
int len = matrix.size();
for (int i = 0; i < len; ++i)
{
if (matrix[i] == 0)
{
matrix[++n2] = 2; matrix[++n1] = 1; matrix[++n0] = 0;
}
else if (matrix[i] == 1)
{
matrix[++n2] = 2; matrix[++n1] = 1;
}
else if (matrix[i] == 2)
{
matrix[++n2] = 2;
}
}
}
void sort_colors_3_pointers(std::vector<int> &matrix)
{
int low = 0;
int mid = 0;
int high = matrix.size() - 1;
while (mid <= high)
{
if (matrix[mid] == 0)
swap(matrix[mid++], matrix[low++]);
else if (matrix[mid] == 1)
mid++;
else
swap(matrix[mid], matrix[high--]);
}
}
int main()
{
//Initialize 1D vector
vector<int> matrix = { 2, 0, 2, 1, 1, 0 };
//sort_colors_in_place(matrix);
sort_colors_3_pointers(matrix);
int len = matrix.size();
cout<<"The sorted array is"<<endl;
for (int i = 0; i < len; ++i)
{
cout<<matrix[i]<<" ";
}
return 0;
}Output:
The sorted array is
0 0 1 1 2 2