Dutch Nation Flag Problem

Problem:

Given an array of red, green and blue balls arrange them in groups of all red together, greens together and blue together. Do in a single scan of the array.

This is same as You have an array containing only '0's, '1's and '2's. Club same items together in single scan.

Solution:

<br />#include<iostream.h><br />#define _SIZE sizeof(a)/sizeof(a[0])<br />using namespace std;<br />void printArray(int *array, int size)<br />{<br />    for(int i=0; i<size; ++i)=""><br />        cout<<array[i]<<" ";<br />    cout<<endl;<br />    return;<br />}<br />void swap(int *a, int left, int right)<br />{<br />    if(a[left] != a[right])<br />    {<br />        a[left] ^= a[right] ^= a[left] ^= a[right];<br />    }<br />}<br />void reArrange(int *a, int length)<br />{<br />    int low, mid, high = length -1;<br />    low =0; mid = 0;<br />    while(mid <= high)<br />    {<br />        switch(a[mid])<br />        {<br />            case 0 :<br />                swap(a, low, mid);<br />                low++;<br />                mid++;<br />                break;<br />            case 1 :<br />                mid++;<br />                break;<br />            case 2 :<br />                swap(a, mid, high);<br />                high--;<br />                break;<br />            default:<br />                cout<<">>> Error \n";<br />        }<br />    }<br />}<br />int main()<br />{<br />    int a [ ] = { 1,1,1,0,1,2,2,1,0,2,1,2,0 };<br />    printArray(a, _SIZE);<br />    reArrange(a, _SIZE);<br />    printArray(a, _SIZE);<br />    return 0;<br />}<br /><br />