# 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.