Sort Binary Array in Linear Time

Given an binary array, sort it in linear time and constant space. Output should print contain all zeroes followed by all ones.

 
For example,


Input: { 1, 0, 1, 0, 1, 0, 0, 1 }

Output:{ 0, 0, 0, 0, 1, 1, 1, 1 }

 


 

Simple solution would be to count number of 0’s present in the array (say k) and fill first k indices in the array by 0 and all remaining indices by 1.

Alternatively, we can also count number of 1’s present in the array (say k) and fill last k indices in the array by 1 and all remaining indices by 0.

C++

Download   Run Code


Java

Download   Run Code



Output:

0 0 0 0 0 0 1 1 1 1

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).

 


 

Instead of counting number of zeroes, if the current element is 0, we can place 0 at next available position in the array. After all elements in the array are processed, we fill all remaining indices by 1.

C++

Download   Run Code


Java

Download   Run Code



Output:

0 0 0 0 0 0 1 1 1 1

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).
 


 

We can also solve this problem in linear time by using partitioning logic of quicksort. The idea is to use 1 as pivot element and make one pass of partition process. The resultant array will be sorted.

C++

Download   Run Code


Java

Download   Run Code



Output:

0 0 0 0 1 1 1 1

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).

 
Exercise:

1. Modify the solution so that all 1’s would come first.

2. Rearrange even and odd numbers in an array in linear time such that all even numbers comes before all odd numbers.

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
Shubham Mathur
Guest
Shubham Mathur
Vishwajeet
Guest
Vishwajeet

Nice Method of Partititioning

wpDiscuz