Jun 112012
 

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

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)