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 🙂
 

Get great deals at Amazon




Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Shubham Mathur
Guest
Shubham Mathur
Vishwajeet
Guest
Vishwajeet

Nice Method of Partititioning

src
Guest

Varun Addepalli
Guest
Varun Addepalli

Time complexity is O(n)

Nishad
Guest
Nishad

Hi, I didn’t get the concept of placing a zero in the next available position in the second proposed solution. What do you mean by next available position? Isn’t the array full of 0’s and 1’s??

Muhammad Amir Pervaiz
Guest
Muhammad Amir Pervaiz

I completed this with one for loop.Code is written is swift. so just two first and last and start comparing and arranging 0’s and 1’s.

var last = sorting.count – 1
var start = 0

for _ in 0..<sorting.count {

if sorting[start] == 0 {
start = start + 1
}
else {
if sorting[last] == 0 {
sorting[start] = 0
sorting[last] = 1
if start == last {
break
}
else {
last = last – 1
}
}
else {
last = last – 1
}
}
}

arandomguy
Guest
arandomguy

isn’t in the partition function, array should be passed by reference?

Ankit
Guest
Ankit

array is passed by reference by default.