Sort An Array Containing zeros, ones and twos in linear time

Given an array containing only zeros, ones and twos. Sort it in linear time.

Test Cases

Sample Input: 0, 1, 2, 2, 1, 0, 0, 2, 0, 1, 1, 0
Expected Output: 0 0 0 0 0 1 1 1 1 2 2 2

Solution

This problem is similar to the problem Sort Binary Array In One Iteration and Quick Sort Partitioning Problem.

We can apply similar logic to this problem.
In the first iteration, we will place all the zeros before ones and twos. (see the image below)

In the next iteration, we will place all the ones before twos but after zeros. (see the image below)

Therefore, at the end of two iterations, the array containing zeros ones and twos will be sorted in linear time. (Since, we are only using two iterations)

Implementation


#include <bits/stdc++.h>
using namespace std;

void swap(vector<int>& vec, int i, int j)
{ 
	int temp = vec[i]; vec[i] = vec[j]; vec[j] = temp; 
	
}
int main() { 
	vector<int> vec = { 0, 1, 2, 2, 1, 0, 0, 2, 0, 1, 1, 0 }; 
	int n = vec.size();
	// In the First Pass, we will sort all the 0s at their correct place 
	int i = -1; 
	for(int j = 0; j < n; j++) 
	{
		if (vec[j] == 0) 
		{ 
			i++; 
			swap(vec, i, j); }
		
	}
	for(int j = 0; j < n; j++)
	{
		if (vec[j] == 1)
		{
			i++;
			swap(vec, i, j);
			
		}
		
	}
	for(int i = 0; i < n; i++)
	{
		cout << vec[i] << " ";
		
	}
	cout << "\n";
}