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

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.
—————————————————————————