The best programs are written so that computing machines can perform
them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist
who works with traditional aesthetic and literary forms as well as mathematical concepts, to
communicate the way that an algorithm works and to convince a reader that the results will be correct.
― Donald E. Knuth

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 arrayvoid 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 spacevoid sort01(int arr[], int size) {
int j = size-1;
int i = 0;
// start traversing the array from endwhile (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 arrayvoid displayArray(int arr[],int size) {
int i;
for(i=0;i<size;i++)
cout<<arr[i]<<" ";
cout<<endl;
}
// mainint 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;
}

#include<iostream>using namespace std;
// swap elements of two indexes in the arrayvoid 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 spacevoid sort01(int arr[], int size) {
int j = size-1;
int i = 0;
// start traversing the array from endwhile (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 arrayvoid displayArray(int arr[],int size) {
int i;
for(i=0;i<size;i++)
cout<<arr[i]<<" ";
cout<<endl;
}
// mainint 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;
}