|
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):
a[1..Lo-1]
zeroes (red)
a[Lo..Mid-1]
ones (white)
a[Mid..Hi]
unknown
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--;
}
}
|
