How to Sort an Array contains 0s,1s ,2s in C++

Hello Friends, Today we are going to learn how to sort an array containing elements as 0,1,2 in C++ program. It seems like an easy question but to solve it with an efficient approach is necessary. I will tell you how to sort the array without using any extra space and time complexity as O(n).

Let’s start with an example for understanding the question first and later on we will see the algorithm as well as code.

EXAMPLE :

array [] = { 0,1,2,1,0,1,2}

Since we know 0<1<2 . ‘0’ will come first then ‘1’ and after that ‘2’.

Output should be :  0,0,1,1,1,2,2 .

Here, I am giving 2 methods for doing this problem . First method is simple approach but not efficient whereas second method is efficient as well as having less lines of codes.

C++ Code for sorting array containing 0,1,2

Method 1:

Time complexity is O(n) and space complexity is O(1).

#include<bits/stdc++.h>
using namespace std;
void sort_0_1_2(int a[],int n); // function prototype

int main()
 {
        int n;       // size of array
        cin >> n;  
        int arr[n];   // suppose input is {0,1,2,1,0,1,2}
        for(int i=0;i<n;i++)
        {
            cin >> arr[i];
        }

        sort_0_1_2(arr, n);

        for(int i=0;i<n;i++)
        {
            cout << arr[i]  << " ";
        }

        cout << endl;      
    
    return 0;
}



void sort_0_1_2(int a[], int n)
{
    int j=0;

    // It will sort element 0
    for(int i=0;i<n;i++)
    {
        if(a[i]==0)
        {
            swap(a[i],a[j]);
            j++;
        }
        else
          continue;
    }
    
    //it will sort element 1
    for(int i=0;i<n;i++)
    {
        if(a[i]==1)
        {
            swap(a[i],a[j]);
            j++;
        }
        else
          continue;
    }

    // It will sort element 2 
    for(int i=0;i<n;i++)
    {
        if(a[i]==2)
        {
            swap(a[i],a[j]);
            j++;
        }
        else
          continue;
    }
}
Output : 0,0,1,1,1,2,2

Understanding the Algorithm

I create a variable j in sort_0_1_2 function which helps in keeping 0,1,2 at correct position. Here, I am traversing the array 3 times. At the first time of traversal, whenever I got 0 , I swapped with index value of j and increment the value of j . By doing that , in first traversal we can ensure that 0 will be placed at correct position.

Similarly, in second and third traversal 1 and 2 will be at correct position.

Method 2 : 

Time Complexity is O(n) and space complexity is O(1).

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

void sort_0_1_2(int a[], int n) 
{ 
  int count0=0,count1=0,count2=0; 
  for(int i=0;i<n;i++)
  {
     if(a[i] == 0)
       count0 ++;
     else if(a[i] == 1)
        count1 ++;
     else if(a[i] == 2)
        count2 ++;
     else
        cout<<"entered element is wrong";
   }

    int temp = 0;
    while (count0 > 0) 
    { 
        a[temp++] = 0; 
        count0--; 
    } 
    while (count1 > 0) 
    { 
        a[temp++] = 1; 
        count1--; 
    } 
    while (count2 > 0)
    { 
        a[temp++] = 2; 
        count2--; 
    } 
} 
int main() 
{ 
    int a[] = {0,1,2,1,0,1,2}; 
    int n = sizeof(a) / sizeof(int); 
    sort_0_1_2(a, n); 
     for (int i = 0; i < n; i++) 
        cout << a[i] << " "; 
   return 0; 
}
Output : 0,0,1,1,1,2,2

Understanding the Algorithm

Here I am counting how many 0,1,2 is there and storing in a variable count0,count1,count2 respectively. After that I know how many 0 is there in an array and how many 1 is there and how many 2. So, i will keep 0,1,2 that number of times in an array .

I hope this tutorial helped you.

You can check out other articles as well

How to Sort array using Stacks in C++

Leave a Reply

Your email address will not be published. Required fields are marked *