- 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