Sort an array of 0s, 1s and 2s Problem
Written by
PROBLEM: An array consists of only 0,1 and 2 as its elements. You have to sort it.
Input: [0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1]
Output: [0,0,0,0,0,1,1,1,1,1,2,2]
# Algorithm
Pseudo Code:
- We will calculate the number of 0s, 1s and 2s in the entire array.
- Thus, get the count of each individual tokens.
- Now, We’ll start from the beginning and place the number of 0s in the starting count_of_zero indices.
- We then place the number of 1s in the next count_of_ones indices.
- At last, we place the number of 2s in the count_of_twos indices.
Code:
#include <bits/stdc++.h> using namespace std;
void sortArray(int arr[], int size) { int iterator, count_of_zeroes = 0, count_of_ones = 0, count_of_twos = 0;
for (iterator = 0; iterator< size; iterator++) { switch (arr[iterator]) { case 0: count_of_zeroes++; break; case 1: count_of_ones++; break; case 2: count_of_twos++; break; } } iterator = 0; while (count_of_zeroes > 0) { arr[iterator++] = 0; count_of_zeroes--; } while (count_of_ones > 0) { arr[iterator++] = 1; count_of_ones--; } while (count_of_twos > 0) { arr[iterator++] = 2; count_of_twos--; } for (int iterator = 0; iterator< size; iterator++) cout << arr[iterator] << " ";
}
int main() { int arr[] = { 0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1 }; cout << "Sorted array is { "; sortArray(arr, 12); cout << "} " << endl; return 0; }
Output:
Sorted array is { 0,0,0,0,0,1,1,1,1,1,2,2 }
Time Complexity: O(N)
Space Complexity: O(1)
This is how we sort an array of 0s 1s and 2s. This is identical to the problem of Dutch National Flag, just using numbers instead of the colors.