Sorting a binary array (which has only 0's and 1's)

Given an array that has only 0's and 1's. Write a function to 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:

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

Time Complexity: O(n.lg(n))     Extra Space: O(1)

Traverse the array and count the zeros in the array. If there are x zeros, then set initial x elements to zero and the 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 (Two-Pointer Approach)

Take two indices, low & high, initially pointing to the first and last elements of the array.

Follow the logic below:

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 L = 0; // LOW
   int H = n-1; // HIGH
   while(L < H)
   {
      // INCREMENT LOW
      while(L<=H && arr[L]==0)
         L++;
      // DECREMENT HIGH
      while(L<=H && arr[high]==1)
         H--;
      // SWAP ELEMENTS AT L and H
      if(L<H)
      {
         int t = arr[L];
         arr[L] = arr[H];
         arr[H] = t;
      }
   }
}

The most common mistake students make in this solution is to not put the check (L<H) in the inner while loop condition. Such a Code will crash if the array has only 0's or 1's (The while condition will never be false and the pointer will go out of array). 

Feel free to feedbback / comment.