Dijkstra used the
Dutch National Flag Problem*
as a structured programming
exercise in program derivation and program proof.
Given `N' objects coloured red, white or blue,
sort them so that objects of the same colour are adjacent,
with the colours in the order red, white and blue.
The problem is closely related to the partition operation of
quick sort:
the attribute need not be a `colour' but can be
`greater than the median', or
`leading digit is zero', or
whatever property you care to choose.
Two Colours
It is easiest to consider just two "colours",
{zero,one}, first.
The algorithm maintains three sections (possibly empty)
in the array a[ ]:
a[1..Lo-1] zeroes
a[Lo..Hi] unknown
a[Hi+1..N] ones
The unknown section is shrunk while maintaining these conditions:
Lo := 1; Hi := N;
while Lo <= Hi do
Invariant: a[1..Lo-1] are all zero and a[Hi+1..N] are all one;
a[Lo..Hi] are unknown.
if a[Lo] = 0 then Lo++
else swap a[Lo] and a[Hi]; Hi--
--- 2-way Partitioning ---
The data in the HTML FORM below consists of random (0|1)s,
generated by Math.random()
(beware there is a bug in MicroSoft Explorer3,
you should be using Netscape3 or later).
In the trace, the parts of the array known to the algorithm,
i.e. a[1..Lo-1] and a[Hi+1..N]
are printed and the unknown section is left blank.
Press the `go' button:
The problem was posed with three colours,
here `0', `1' and `2'.
The array is divided into four sections:
a[1..Lo-1] zeroes (red)
a[Lo..Mid-] ones (white)
a[Mid..Hi] unknown
a[Hi+1..N] twos (blue)
The unknown region is shrunk while maintaining these conditions
Lo := 1; Mid := 1; Hi := N;
while Mid <= Hi do
Invariant: a[1..Lo-1]=0 and a[Lo..Mid-1]=1 and a[Hi+1..N]=2;
a[Mid..Hi] are unknown.
case a[Mid] in
0: swap a[Lo] and a[Mid]; Lo++; Mid++
1: Mid++
2: swap a[Mid] and a[Hi]; Hi--
--- Dutch National Flag Algorithm, or 3-way Partitioning ---
Part way through the process,
some red, white and blue elements are known and are
in the "right" place.
The section of unknown elements, a[Mid..Hi],
is shrunk by examining a[Mid]:
|
0 0 0 1 1 1 ? ? ? ? 2 2 2
^ ^ ^
| | |
Lo Mid Hi
Examine a[Mid]. There are three possibilities:
a[Mid] is (0) red, (1) white or (2) blue.
Case (0) a[Mid] is red, swap a[Lo] and a[Mid]; Lo++; Mid++
0 0 0 0 1 1 1 ? ? ? 2 2 2
^ ^ ^
| | |
Lo Mid Hi
Case (1) a[Mid] is white, Mid++
0 0 0 1 1 1 1 ? ? ? 2 2 2
^ ^ ^
| | |
Lo Mid Hi
Case (2) a[Mid] is blue, swap a[Mid] and a[Hi]; Hi--
0 0 0 1 1 1 ? ? ? 2 2 2 2
^ ^ ^
| | |
Lo Mid Hi
Continue until Mid>Hi.
Demonstration
The data in the HTML FORM below consists of random (0|1|2)s.
In the trace, the parts of the array known to the algorithm,
i.e. a[1..Mid-1] and a[Hi+1..N]
are printed and the unknown section is left blank.
Press the `go' button:
When the items being sorted are literally just integers in [0..1] or [0..2]
one could just count the number of each value and overwrite the array
contents accordingly. However the intent is that the array items are
reasonably complex and that they happen to have an attribute (~colour)
drawn from a 2-value or 3-value data-type.
The DNF algorithm can be extended to four, or even more colours
but it grows more and more complex to write,
and the constant of proportionality in its running time increases.
The DNF algorithm can be used to partition
an array into sections that are
(i) <x (red),
(ii) =x (white), and
(iii) >x (blue),
where x is an estimate of the median, for example.
Sections (i) and (iii) can be sorted recursively as in Quick Sort.
An alternative to the previous point is to find two different elements,
v1 and v2, from the array such that v1<v2
(it's sorted if you can't find such v1 and v2), and
partition the array into sections
(i) <=v1 (red),(ii) >v1 and <=v2; (white), and
(iii) >v2 (blue).
Each of the three sections ((iii) might be empty)
can then be sorted recursively
giving a 3-way Quick Sort.