Sort colors is a problem in which we have to given an array containing N objects. Each box is painted with a single color which can be red, blue, and white. We have N objects which are already painted. We have to sort the array such that the same color objects come continuously. Here Red color denoted by 0, White color denoted by 1, and Blue color denoted by 2 respectively. Let’s see an example described in the below image. In the image, we see clearly that all the same color objects are adjacent to each other. Two red objects, three white objects, and three blue objects are arranged in sorted order.
Note: We can’t use any predefined library function to sort the N objects.
Table of Contents
Input Format
First-line containing an integer which denotes the number of objects in the array.
Second-line containing the N integers.
Output
Print the sorted array such that two same-color objects are always adjacent to each other.
Constraints
- 1<=N<=100000
- 0<=a[i]<=2
6 0 1 0 2 1 2
0 0 1 1 2 2
Explanation
We just use 3 variables to count the number of 0,1 and 2. After counting we first set all the zero to beginning using the count of zero variable.
And after it set all the ones and at the end set all the two’s.
Algorithm For Sort Colors
Step:1 Set zero_count=0,one_count=0,two_count=0.
Step:2 For i in range 0 to N-1:
If a[i] = 0 then:
zero_count++.
If a[i] = 1 then:
one_count++.
If a[i] = 2 then:
two_count++.
Step:3 Set i=0.
Step:4 While(zero_count>0) then:
a[i] = 0.
zero_count--;
Step:5 While(one_count>0) then:
a[i] = 1.
one_count--;
Step:6 While(two_count>0) then:
a[i] = 0.
two_count--;
Step:7 Print the final array a.Implementation For Sort Colors
/*C++ Implementation of Sort Colors.*/
#include<bits/stdc++.h>
using namespace std;
int main()
{
/*input values.*/
int n;
cin>>n;
int a[n];
int zero_count=0,one_count=0,two_count=0;
for(int i=0;i<n;i++)
{
cin>>a[i];
/*count all the same color objects.*/
if(a[i]==0)
{
zero_count++;
}
else if(a[i]==1)
{
one_count++;
}
else
{
two_count++;
}
}
int i=0;
/*all objects with red color.*/
while(zero_count>0)
{
a[i]=0;
zero_count--;i++;
}
/*all object with white color.*/
while(one_count>0)
{
a[i]=1;
one_count--;i++;
}
/*all object with blue color.*/
while(two_count>0)
{
a[i]=2;
two_count--;i++;
}
/*print final result.*/
for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
return 0;
}6 1 2 1 0 2 0
0 0 1 1 2 2
Time Complexity
O(N) because we print the N values of the given array. Here we run one linear loop to print the final result.
Space Complexity
O(1) because we just use the 3 variables to count the same color objects.