While preparing my lecture notes on sorting, I rediscovered the *Dutch flag problem* proposed by Edsger W. Dijkstra quite a while ago. This problem is relevant in the context of sorting, especially for variants of Quicksort, where you want to create not two but three partitions.

Like many problems, the Dutch flag problem has a very simple statement. Say you have an array with three types of value, how can you arrange them so that all the items of the first type is at the beginning of the array, the items of the third at the end (and, of course, leaving the second type between the two)?

Well, let see how we can arrive to an efficient algorithm to do this. If we take the type as being the only information contained in the items, we could do this in exactly linear time by counting how many items falls in each category and paint back the array with the appropriate number of items. This also require a constant amount of auxiliary storage because we would need only two counters (the third being implied, since ).

If the category—let’s call that the color, since we’re talking about the Dutch flag—is but one of the characteristics of the items, then the count-and-repaint method is insufficient. We must have a partition-type algorithm where items are shifted around to create the desired arrangement.

In Quicksort, the partition algorithm creates on an array two partitions, one partition with all the values smaller than the pivot value, and the other with all value greater than or equal to the pivot value. It does so by using two cursors, one starting at the beginning (at the left) of the array the other at the end (to the right), and iterating as follows. If the value under the left cursor is smaller than the pivot, we advance the cursor. If the value under the right cursor is larger or equal to the pivot, we move the cursor left once. We are now in a position where the value under the left cursor is greater or equal than the pivot and the value under the right cursor is smaller than the pivot: we swap the values, advance the left cursor and move the right cursor down once. When the cursors meet somewhere in the middle of the array, the partition is complete. Quicksort then proceeds to recursively sort both partitions.

We will take a similar approach, but now we have a third partition. We want to have a partition with all values smaller than the pivot, one with the values equal to the pivot, and one with all values larger than the pivot. Now, instead of two cursor, we will need three: one at the end of the ‘red’ partition, one at the end of the ‘white’ partition, and a third at the base of the ‘blue’ partition. In the beginning, the first two cursor point at the base of the array while the third points to its last element.

The partition works by moving an out-of-order item to the middle partition then moving it to the correct end, if it’s not already there. The middle cursor points to the next item to examine. If it’s red, we swap it with the base of the white partition, and advance both cursors as the order is preserved. If it’s blue, we swap it with the last not yet sorted item and merge it with the blue partition. The algorithm stops when the unsorted cursor meets the cursor of the blue partition.

An simple implementation in C++ would be somethin’ like this:

typedef enum { red, white, blue } color; void three_color_sort(std::vector<color> & colors) { if (colors.size()==0) return; size_t r=0; // top red size_t w=0; // top white size_t b=colors.size()-1; // base blue while (w<b) { if (colors[w]==red) { std::swap(colors[r],colors[w]); r++; w++; } else if (colors[w]==blue) { std::swap(colors[w],colors[b]); b--; } else w++; // colors[w]==white show(colors); } }

And we can verify that it, indeed, works:

..r.b..rr.b.b.b.rr..bbrrbbb...brrrbr.... ..r.b..rr.b.b.b.rr..bbrrbbb...brrrbr.... r...b..rr.b.b.b.rr..bbrrbbb...brrrbr.... r...b..rr.b.b.b.rr..bbrrbbb...brrrbr.... r......rr.b.b.b.rr..bbrrbbb...brrrbr...b r......rr.b.b.b.rr..bbrrbbb...brrrbr...b r......rr.b.b.b.rr..bbrrbbb...brrrbr...b r......rr.b.b.b.rr..bbrrbbb...brrrbr...b rr......r.b.b.b.rr..bbrrbbb...brrrbr...b rrr.......b.b.b.rr..bbrrbbb...brrrbr...b rrr.......b.b.b.rr..bbrrbbb...brrrbr...b rrr.........b.b.rr..bbrrbbb...brrrbr..bb rrr.........b.b.rr..bbrrbbb...brrrbr..bb rrr.........b.b.rr..bbrrbbb...brrrbr..bb rrr...........b.rr..bbrrbbb...brrrbr.bbb rrr...........b.rr..bbrrbbb...brrrbr.bbb rrr...........b.rr..bbrrbbb...brrrbr.bbb rrr.............rr..bbrrbbb...brrrbrbbbb rrr.............rr..bbrrbbb...brrrbrbbbb rrr.............rr..bbrrbbb...brrrbrbbbb rrrr.............r..bbrrbbb...brrrbrbbbb rrrrr...............bbrrbbb...brrrbrbbbb rrrrr...............bbrrbbb...brrrbrbbbb rrrrr...............bbrrbbb...brrrbrbbbb rrrrr...............rbrrbbb...brrrbbbbbb rrrrrr...............brrbbb...brrrbbbbbb rrrrrr...............brrbbb...brrrbbbbbb rrrrrr...............rrrbbb...brrbbbbbbb rrrrrrr...............rrbbb...brrbbbbbbb rrrrrrrr...............rbbb...brrbbbbbbb rrrrrrrrr...............bbb...brrbbbbbbb rrrrrrrrr...............rbb...brbbbbbbbb rrrrrrrrrr...............bb...brbbbbbbbb rrrrrrrrrr...............rb...bbbbbbbbbb rrrrrrrrrrr...............b...bbbbbbbbbb rrrrrrrrrrr...............b...bbbbbbbbbb rrrrrrrrrrr..................bbbbbbbbbbb rrrrrrrrrrr..................bbbbbbbbbbb rrrrrrrrrrr..................bbbbbbbbbbb

*

* *

the complexity of the partition is , that is, exactly of the order of because each element is examined and placed once. This is very efficient, but the algorithm has the limitation of requiring random accesses to memory, and does not limit itself to sequential reads. However, it’s still quite efficient because it requires only three regions to be maintained in cache.