#### Arrays & Strings

**Problem **

Sort an array of **0**s & **1**s, 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 **0**s will form one portion of the array and all **1**s 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; }