Dutch national flag problem

From Wikipedia, the free encyclopedia

Dutch national flag redirects here. For the flag, see Flag of the Netherlands.

The Dutch national flag problem is a famous problem proposed by Edsger Dijkstra. The flag of the Netherlands consists of three colors : Red, White and Blue. Given balls of these three colors arranged randomly in a line (the actual number of balls does not matter), the task is to arrange them such that all balls of same color are together. This problem can also be viewed in terms of rearranging elements in an array.

In array context, the problem is to 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.