(classic problem)
Definition: Rearrange elements in an array into three groups: bottom, middle, and top.
One algorithm is to have the top group grow down from the top of the array, the bottom group grow up from the bottom, and keep the middle group just above the bottom. The algorithm stores the locations just below the top group, just above the bottom, and just above the middle in three indexes. At each step, examine the element just above the middle. If it belongs to the top group, swap it with the element just below the top. If it belongs in the bottom, swap it with the element just above the bottom. If it is in the middle, leave it. Update the appropriate index. Complexity is Θ(n) moves and examinations.
Generalization (I am a kind of ...)
partition.
Aggregate parent (I am a part of or used in ...)
multikey Quicksort.
See also American flag sort.
Note: Using this algorithm in quicksort to partition elements, with the middle group being elements equal to the pivot, lets quicksort avoid "resorting" elements that equal the pivot.
Author: PEB
A detailed tutorial on the algorithm. The flag of the Netherlands or the Dutch national flag.
James R. Bitner, An Asymptotically Optimal Algorithm for the Dutch National Flag Problem, SIAM Journal on Computing, 11(2):243-262, May 1982.
Colin L. McMaster, An Analysis of Algorithms for the Dutch National Flag Problem, CACM, 21(10):842-846, October 1978.
E. W. Dijkstra, A Discipline of Programming, Prentice-Hall, 1976.
Historical Note
Lloyd Allison reports that Dijkstra used this problem as an exercise in program derivation and program proof. Allison first heard about the problem at the Institute of Computer Science (ICS), London University, about 1973. The algorithm is named for the problem of ordering red, white, and blue marbles into the order of the Dutch national flag.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 28 December 2006.
HTML page formatted Mon Feb 2 13:10:39 2015.
Cite this as:
Paul E. Black, "Dutch national flag", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 28 December 2006. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/DutchNationalFlag.html