Dutch national flag
From Wikipedia, the free encyclopedia
- This article is about the algorithm. For the flag, see Flag of the Netherlands.
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.
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.
[edit] See also
Paul E. Black, Dutch national flag at the NIST Dictionary of Algorithms and Data Structures.
