We represent color red, white, and blue with integers 0, 1, and 2 to represent respectively.
Example:
|
1 2 |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
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 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
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 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
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 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
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 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
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 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
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:
|
1 2 3 4 5 6 7 8 9 |
while (mid <= high) { if (arr[mid] == 0) swap(arr[mid++], arr[low++]); else if (arr[mid] == 1) mid++; else swap(arr[mid], arr[high--]); } |
|
1 2 3 4 5 6 7 8 9 10 |
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 |
|
1 2 3 |
In the begenning of pass 2 values are: low = 0 mid = 0 high = 4 Input array = 0 0 2 1 1 2 |
|
1 2 3 |
In the begenning of pass 3 values are: low = 1 mid = 1 high = 4 Input array = 0 0 2 1 1 2 |
|
1 2 3 |
In the begenning of pass 4 values are: low = 2 mid = 2 high = 4 Input array = 0 0 2 1 1 2 |
|
1 2 3 |
In the begenning of pass 5 values are: low = 2 mid = 2 high = 3 Input array = 0 0 1 1 2 2 |
|
1 2 3 4 5 |
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++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
#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:
|
1 2 |
The sorted array is 0 0 1 1 2 2 |
