Sort an array of 0s & 1s. Implement an efficient algorithm

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.