Program to Separate 0 and 1 in an Array

  • Write a program to segregate 0 and 1 in linear time complexity.
  • How to separate 0 and 1 using Dutch Flag Algorithm.

Given an array of integers of size N having only 0 and 1. We have to separate 0 and 1 in an array. First group all 0's then all 1's.
For Example :
Input Array : 0 1 1 1 0 0 0 1 0 1
Output Array : 0 0 0 0 0 1 1 1 1 1

Method 1 : By Counting Number of Zero's in array.
Let inputArray be an integer array of size N having only 0 and 1.
  • Using a loop, traverse inputArray from index 0 ti N-1.
  • Count the number of 0's in inputArray and store it in a variable zeroCount. Hence, the number of 1's in inputArray is equal to N-zeroCount.
  • Set first "zeroCount" elements to 0, and remaining elements(N - zeroCount) to 1.
Time Complexity : O(n)

C program to separate 0 and 1 by counting 0's

#include 

/* Returns number of zero in array */
int countZero(int *array, int size){
    int count = 0, i;
    for(i=0; i < size; i++){
        if(array[i] == 0)
            count++;
    }
    return count;
}

/*Seperates 0 and 1 in an array. 
first all 0's and then all 1's*/
void seperateOAnd1(int *array, int size){
    int i, zeroCount = countZero(array, size);
 /* Populate first zeroCount indexes with 0 
 and then remaining with 1*/
 for(i = 0; i < size; i++){
     if(i < zeroCount)
                array[i] = 0;
            else 
                array[i] = 1;
 } 
}

int main(){
    int array[10] = {0, 1, 1, 0, 0, 1, 0, 1, 0, 0}; 
    int i;
    
    seperateOAnd1(array, 10);
    
    for(i = 0; i < 10; i++){
     printf("%d ", array[i]);
    }

    return 0;
}
Output
0 0 0 0 0 0 1 1 1 1
Method 2 : By using Dutch Flag Algorithm.
Let inputArray be an integer array of size N having only 0 and 1.
  • Initialize two variables leftIndex and rightIndex to index 0 and N-1.
  • Find first 1 by moving leftIndex from left to right
  • Find first 0 by moving rightIndex from right to left.
  • Swap array[leftIndex] and array[rightIndex].
  • Repeat above process till rightIndex > leftIndex.
Time Complexity : O(n)

C program to separate 0 and 1 by counting 0's

#include <stdio.h>

/*Seperates 0 and 1 in an array. first all 0's and then all 1's.
This approach is similar to partition step of quick sort */
void seperateOAnd1(int *array, int size){
    int temp, left = 0, right = size-1;
    while(right > left){
     /* traverse from left to right till we find a 1 */
     while(array[left] != 1)
         left++;
     /* traverse from right to left till we find a 0 */
     while(array[right] != 0)
         right--;
     
     if(left < right){
            /* Swap array[left] and array[right] */
            temp = array[left];
            array[left] = array[right];
            array[right] = temp;
        }
    }
}

int main(){
    int array[10] = {0, 1, 1, 0, 0, 1, 0, 1, 0, 0}; 
    int i;
    
    seperateOAnd1(array, 10);
    
    for(i = 0; i < 10; i++){
     printf("%d ", array[i]);
    }

    return 0;
}
Output
0 0 0 0 0 0 1 1 1 1
Posted by
Labels: ,