# Interview Questions

# Sorting a binary array (which has only 0 & 1)

- June 11, 2012
- Posted by: Kamal Rawat
- Category: Algorithms

Given an array which has only 0’s and 1’s. Write an algorithm which will sort this array. (i.e separate 0’s and 1’s by bringing 0’s before 1’s).

Input Array: {0, 1, 1, 0, 0, 0, 0, 1, 1, 0} Output Array: {0, 0, 0, 0, 0, 0, 1, 1, 1, 1}

### Solution:

There are multiple methods to sort the array:

**Method-1: Use conventional sorting algorithms**

You may choose to sort them using conventional sorting algorithms like Quick Sort.

**Time Complexity:** O(n.lg(n))

**Extra Space:** O(1)

**Method-2: Count 0’s or 1’s**

Traverse the array and count the zero’s in the array. If there are x zeros, then set initial x elements to zero and rest (n-x) elements to 1.

void sort(int *arr, int n) { int zeroCnt = 0; int i; // Counting the zeros for(i=0; i<n; i++) if(arr[i] == 0) zeroCnt++; // setting first x elements to zero for(i=0; i<x; i++) arr[i] = 0; for(i=x; i<n; i++) arr[i] = 1; }

**Method-3: Use one pass of Quick Sort**

Take two indexes low & high initially pointing to the first and last elements of the array. Follow the below logic:

while(low < high)

1. Increment low till arr[low] is zero

2. decrement high till arr[high] is one

3. if(low<high) swap arr[low] & arr[high]

void sort(int *arr, int n) { int low = 0; int high = n-1; while(low<high) { // Incrementing Low while(arr[low]==0) low++; // decrementing high while(arr[high]==1) high--; // swapping elements at low & high if(low<high) { int t = arr[low]; arr[low] = arr[high]; arr[high] = t; } } }

Feel free to feedbback / comment.

—————————————————————————