ProDeveloperTutorial.com

Tutorials and Programming Solutions
Menu
  • Shell Scripting
  • System Design
  • Linux System Programming
  • 4g LTE
  • Coding questions
  • C
  • C++
  • DSA
  • GIT
  • 450 DSA Cracker
  • 5G NR
  • O-RAN

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

prodevelopertutorial August 29, 2018

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]

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

 

List Of Tutorials available in this website:

C Programming 20+ ChaptersC++ Programming 80+ Chapters
100+ Solved Coding QuestionsData Structures and Algorithms 85+ Chapters
System design 20+ ChaptersShell Scripting 12 Chapters
4g LTE 60+ ChaptersMost Frequently asked Coding questions
5G NR 50+ ChaptersLinux System Programming 20+ chapters

 

Share
Email
Tweet
Linkedin
Reddit
Stumble
Pinterest
Prev Article
Next Article

About The Author

prodevelopertutorial

Follow this blog to learn more about C, C++, Linux, Competitive Programming concepts, Data Structures.

ProDeveloperTutorial.com

Tutorials and Programming Solutions
Copyright © 2022 ProDeveloperTutorial.com