#### Arrays & Strings

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

Solution
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);
cout<<"\nOriginal Array :-";
displayArray(arr,size);
sort012(arr,size);
cout<<"\nSorted Array :-";
displayArray(arr,size);
cout<<endl;
return 0;
}```