Make delicious recipes!


Dutch National Flag Problem


Sort an array of balls having colors R, W and B such that all balls with the same color are contiguous (i.e. form one group for each color).

Solution: Let us do it for two colors first.
int lo = 1;
int hi = arr.length-1;

while (lo < hi)
{
    if (arr[lo] == 0)
    {
        lo++;
    }
    else
    {
        swap (arr, lo, hi);
        hi--;
    }
}



For 3 colors, we will maintain 4 regions, demarcated by 3 positions (Lo, Mid and Hi):
  1. a[1..Lo-1] zeroes (red)

  2. a[Lo..Mid-1] ones (white)

  3. a[Mid..Hi] unknown

  4. a[Hi+1..N] twos (blue)


The unknown region is shrunk while maintaining these conditions by the following code:
int lo  = 1;
int mid = 1;
int hi  = arr.length-1;

while (mid < hi)
{
    if (arr[mid] == 0)
    {
        swap (arr, lo, mid);
        lo++;
        mid++;
    }
    else if (arr[mid] == 1)
    {
        mid++;
    }
    else if (arr[mid] == 2)
    {
        swap (arr, mid, hi);
        hi--;
    }
}






Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal