C Program to Sort an Array Containing 0, 1 and 2.

  • Write a program to sort an array containing only 0, 1 and 2.
  • Dutch flag algorithm to re arrange 0, 1 and 2 such that first all 0's then all 1's and at last all 2's.

Given an array of size N containing 0, 1 and 2. We have to sort this array such that all zero's are grouped at the beginning then all one's and at last all two's are grouped together. 

Input Array : [0 1 1 2 2 0 0 2 1 1 0]
Output Array : [0 0 0 0 1 1 1 1 2 2 2]

Let inputArray be an integer array of 0, 1 and 2 of size N.
By counting number os 0, 1 and 2
  • Traverse inputArray and count the frequency of 0, 1 and 2 and store it in zeroCount, oneCount, twoCount respectively.
  • Now, set first "zeroCount" array elements to 0, then next "oneCount" element to 1 and set last "twoCount" element to 2.
By using Dutch Flag Algorithm
  • Initialize zeroIndex and oneIndex to 0 and twoIndex to N-1.
  • At any moment of time, all the elements from 0 to zeroIndex are 0. All elements between zeroIndex to oneIndex are 1 and all elements from twoIndex till N-1 are 2.
  • Elements between oneIndex and twoIndex are unarranged.
  • Traverse inputArray using oneIndex.
    • If inputArray[oneIndex] == 0, then swap elements at zeroIndex and oneIndex. Increment zeroIndex and oneIndex.
    • If inputArray[oneIndex] == 1, then increment oneIndex.
    • If inputArray[oneIndex] == 2, then swap element at oneIndex and twoIndex. Decrement twoIndex.
  • Continue until oneIndex <= twoIndex.

C program to sort an array containing 0, 1 and 2.

#include <stdio.h>

/* Swaps two element of array at index i and j */
void swap(int *array, int i, int j){
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

/*Seperates 0, 1 and 2 in an array. first all 0's and 
then all 1's and then all 2. This algorithm is known as 
Dutch Flag Algorithm */
void seperateNumbers(int *array, int size){
    int zeroIndex = 0, oneIndex = 0, twoIndex = size-1;
    while(oneIndex <= twoIndex){
        switch(array[oneIndex]) {
           case 0 : {
                swap(array, zeroIndex++, oneIndex++);
                break;
                    }
           case 1 : {
                oneIndex++;
                break;
                    }
           case 2 :{
                swap(array, oneIndex, twoIndex--);
                   }
        }
    }
}

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

    return 0;
}
Output
0 0 0 0 1 1 1 1 2 2 2 2