Question : An array is given with 0’s ,1’s and 2’s .Without using any extra space and sorting algorithm put all 0’s first, then all 1’s and all 2’s in last.
Examples : Input: {0, 1, 2, 0, 1, 2} Output: {0, 0, 1, 1, 2, 2}
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}

Solution : This problem is based on famous Dutch National Flag Algorithm .

Here we need three variables : low , mid and high . This algorithm is based on the fact that , all the numbers from 0 to (low-1) are 0s and from (high+1) to n that is the size of array is 2. That means all the elements towards left side of low is zeroes and right side of high is twoes.We will take low pointer at zeroth index of the array and high pointer at (n-1)th index of an array.

We are going to take another pointer as mid and going to move this.We will be moving mid pointer till we cross the high pointer.

While moving the mid pointer we are going to have three checks :
1.when array[mid]=0 ; swap array[low] with array[mid] ; then move mid and low both pointer by one index .
2.When array[mid]=1 ; move mid pointer by one.
3.when array[mid]=2 ; swap array[mid] with array[high] ; then decrease high pointer by one.

We will move from 0th index of the array with mid pointer and continue above three checks till mid reaches high pointer.

Code :
C++

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

void solve(int a[], int n)
{
	int low=0;
        int mid=0;
        int high=n-1;
        
        while(mid<=high)
        {
            if(a[mid]==0)
            {
                swap(a[low],a[mid]);
                low++;
                mid++;
                
            }
            else if(a[mid]==1)
            {
                 mid++;
            }
            else
            {
                swap(a[mid],a[high]);
                high--;
                
            }
            
        }
    for (int i = 0; i < n; i++)
     {cout << a[i] << " ";}
  
}

int main()
{
    int n;
    cin>>n;
    int ar[n];
    for(int i=0;i<n;i++){
      cin>>ar[i];
    }
    solve(ar,n);
    return 0;
}

Commands :
Compile : g++ filename.cpp
Run : ./a.out (ubuntu terminal)