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.

darkmode