the Dutch Flag Problem

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.

dutch-flag

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 c_3=n-c_1-c_2).

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 \Theta(n), that is, exactly of the order of n 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: