#### Arrays & Strings

Problem
Sort an array of 0s & 1s, i.e element at each index of the array is either 0 or 1. Implement an efficient algorithm so that the array gets sorted (all ‘0’s are placed before ‘1’s)

Solution
First approach that we might think of is counting the no. of ‘0’s (say ‘m’) and ‘1s’ (say ‘n’) and then placing m ‘0’s and n ‘1’s. Well, this approach is efficient with complexity of O(n) but it requires traversing the array 2 times. So, as soon as you suggest this approach, interviewer would ask for a better solution.
Following implementation sorts the array in 1 pass.
Say ‘i’ points to index 0 & ‘j’ points to index n-1.
We will start traversing from end of the array.
If arr(j) is 0, then swap arr(i) & arr(j) and increment ‘i’ else decrement ‘j’.
In this way all 0s will form one portion of the array and all 1s will form other portion.

```#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 in 1 pass with no extra space
void sort01(int arr[], int size) {
int j = size-1;
int i = 0;
// start traversing the array from end
while (j >= i ) {
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,i,j);
i++;
}
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[] = {0,1,0,1,1,0,1,0,0,1,0};
int size = sizeof(arr)/sizeof(arr[0]);
cout<<"\nOriginal Array :-";
displayArray(arr,size);
sort01(arr,size);
cout<<"\nSorted Array :-";
displayArray(arr,size);
cout<<endl;
}```