**Problem :- **

Sort an array of **0**s, **1**s & **2**s, i.e
element at each index of the array is either **0**, **1** or **2** and we need to place all **0**s first, then **1**s
and finally all **2**s.

**Solution :- **

After implementing an efficient algorithm to sort an array of **0**s &
**1**s, a very common follow up question is to sort the array of **0**s, **1**s & **2**s.

Again, we won't consider the counting approach rather would go for a 1 pass approach in which the sorting would be done by traversing
the array only once.

We need to divide the array into 3 parts.

Say **'i'** points to index **0** & **'j'** points to index **n-1**.

We will start traversing from the end of array & **'k'** is the iterator starting at index **n-1**.

If **arr(k)** is **0**, then swap **arr(i)** & **arr(k)** and increment **'i'**.

If **arr(k)** is **2**, then swap **arr(j)** & **arr(k)** and decrement **'j'**.

If **arr(k)** is **1**, then don't do anything, simple decrement the iterator **'k'**.

In this way, the array will be divided into 3 portions.

**#include<iostream>**
**using namespace** std;
*// swap elements of two indexes in the array*
**void** swap (**int** arr[], **int** pos1, **int** pos2) {
**int** temp = arr[pos1];
arr[pos1] = arr[pos2];
arr[pos2] = temp;
}
*// sort the array of 0,1,2 in 1 pass with no extra space*
**void** sort012(**int** arr[], **int** size) {
**int** start = 0;
**int** end = size-1;
**int** j = end;
*// start traversing from end
// maintain two pointers
// start -> '0' boundary from left
// end -> '2' boundary from right
// j -> iterator*
**while** (j >= start) {
**if** (arr[j] == 0) {
*// move the 0 to the portion of array
// where all 0s present and increase the
// 0 boundary towards right*
swap(arr,start,j);
start++;
}
**else if** (arr[j] == 2) {
*// move the 2 to the portion of array
// where all 2s present and increase the
// '2' boundary towards left*
swap(arr,j,end);
end--;
}
**else** {
*// don't do anything if '1' is found*
j--;
}
}
}
*// display the array*
**void** displayArray(**int** arr[],**int** size) {
**int** i;
**for**(i=0;i<size;i++)
cout<<arr[i]<<" ";
cout<<endl;
}
*// main*
**int** main() {
**int** arr[] = {1,2,0,1,0,1,2,0,2,0,0,2,1,0,1,0};
**int** size = **sizeof**(arr)/**sizeof**(arr[0]);
cout<<"\nOriginal Array :-";
displayArray(arr,size);
sort012(arr,size);
cout<<"\nSorted Array :-";
displayArray(arr,size);
cout<<endl;
**return** 0;
}