(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 O(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.
The first reference I have to this algorithm is the report of someone hearing it at a lecture 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.
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.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified Wed Dec 14 12:58:44 2005.
HTML page formatted Thu Dec 15 09:30:41 2005.
Cite this as:
Paul E. Black, "Dutch national flag", from
Dictionary of Algorithms and Data
Structures, Paul E. Black, ed.,
NIST.
http://www.nist.gov/dads/HTML/DutchNationalFlag.html
