Recent Posts

Sort an array of 0s, 1s and 2s Problem

Written by

Anshuman Raina

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:

  1. We will calculate the number of 0s, 1s and 2s in the entire array.
  2. Thus, get the count of each individual tokens.
  3. Now, We’ll start from the beginning and place the number of 0s in the starting count_of_zero indices.
  4. We then place the number of 1s in the next count_of_ones indices.
  5. 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&lt; 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 &gt; 0)
{
	arr[iterator++] = 0;
	count_of_zeroes--;
}

while (count_of_ones &gt; 0)
{
	arr[iterator++] = 1;
	count_of_ones--;
}

while (count_of_twos &gt; 0)
{
	arr[iterator++] = 2;
	count_of_twos--;
}

for (int iterator = 0; iterator&lt; size; iterator++)
	cout &lt;&lt; arr[iterator] &lt;&lt; " ";



}


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.

 

Sort an array of 0s, 1s and 2s Problem