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

                                      

an array of  0s, 1s and 2s is given , we should sort the array . 0s first, then all 1s and all 2s in last.

example

Input: {0, 1, 2, 0, 1, 2, 0, 1, 1}
Output:{0, 0, 0, 1, 1, 1, 1, 2, 2}

easy method:

use the inbuild sort function in c++:

implementation c++:

void sort012(int a[], int n)
{
    sort(a,a+n);
}

• Time Complexity: O(nlogn).
  as sort function O(nlogn) time to sort an array.
• Space Complexity: O(1).
  No extra space is required.

method 2:

1)count the numberof 0's , 1's , 2's by using 3 variables and incrementing them.

2) now store all the 0s in the beginning followed by all the 1s then all the 2s.

implementation in c++:

void sortArr(int arr[], int n) 
{ 
    int i, cnt0 = 0, cnt1 = 0, cnt2 = 0; 
  
    // Count the number of 0s, 1s and 2s in the array 
    for (i = 0; i < n; i++) { 
        switch (arr[i]) { 
        case 0: 
            cnt0++; 
            break; 
        case 1: 
            cnt1++; 
            break; 
        case 2: 
            cnt2++; 
            break; 
        } 
    } 
  
    // Update the array 
    i = 0; 
  
    // Store all the 0s in the beginning 
    while (cnt0 > 0) { 
        arr[i++] = 0; 
        cnt0--; 
    } 
  
    // Then all the 1s 
    while (cnt1 > 0) { 
        arr[i++] = 1; 
        cnt1--; 
    } 
  
    // Finally all the 2s 
    while (cnt2 > 0) { 
        arr[i++] = 2; 
        cnt2--; 
    } 
}

• Time Complexity: O(n).
  Only two traversals of the array is needed.
• Space Complexity: O(1).
  As no extra space is required.