An Analysis of Algorithms for the Dutch National Flag Problem

Solutions to the Dutch National Flag Problem
have been given by Dijkstra [1] and Meyer [3]. 
 Dijkstra starts with a simple program and arrives at
an improved program by refinement.  Both of the 
algorithms given by Dijkstra are shown to have an expected number
of swaps which is 2/3N + 0(1) and that 
these values differ at most by 1/3 of a swap and asymptotically
by 1/4 of a swap.  The algorithm of Meyer 
is shown to have expected swap complexity 5/9N.

CACM October, 1978

McMaster, C.

Algorithmic analysis, Dutch National Flag
Problem, refinement, structured programming

4.0 5.24 5.25 5.3

CA781006 DH January 29, 1979  5:47 PM

3055	5	3055
3055	5	3055
3055	5	3055
3170	5	3055
3055	6	3055
3104	6	3055