Given an array with element colored red, white or blue, sort them in-place, with the colors in the order red, white and blue in CPP

We represent color red, white, and blue with integers 0, 1, and 2 to represent respectively.

Example:

Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

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 the 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.

Pseudocode:

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:

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--]);
}

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++

#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