Dutch National Flag Problem

Two Colours

It is easiest to consider just two "colours", {zero,one}, first. The algorithm maintains three sections (possibly empty) in the array a[ ]:

1. a[1..Lo-1] zeroes
2. a[Lo..Hi] unknown
3. a[Hi+1..N] ones

The unknown section is shrunk while maintaining these conditions:

1. Lo := 1; Hi := N;
2. while Lo <= Hi do
   1. Invariant: a[1..Lo-1] are all zero and a[Hi+1..N] are all one; a[Lo..Hi] are unknown.
   2. if a[Lo] = 0 then Lo++
   3. else swap a[Lo] and a[Hi]; Hi--

The problem was posed with three colours, here `0', `1' and `2'. The array is divided into four sections:

1. a[1..Lo-1] zeroes (red)
2. a[Lo..Mid-] ones (white)
3. a[Mid..Hi] unknown
4. a[Hi+1..N] twos (blue)

The unknown region is shrunk while maintaining these conditions

1. Lo := 1; Mid := 1; Hi := N;
2. while Mid <= Hi do
   1. Invariant: a[1..Lo-1]=0 and a[Lo..Mid-1]=1 and a[Hi+1..N]=2; a[Mid..Hi] are unknown.
   2. case a[Mid] in
      • 0: swap a[Lo] and a[Mid]; Lo++; Mid++
      • 1: Mid++
      • 2: swap a[Mid] and a[Hi]; Hi--

Read full article from Dutch National Flag Problem