The Dutch National Flag

Here's a coding challenge that is as old as computer science itself.  Can you sort an array containing values of three different types, in place?  Read on for some insights on a surprisingly hard coding problem. The Dutch National Flag is a programming problem proposed by programming pioneer Edsger W. Dijkstra more than 40 years ago.  The Dutch flag consists of three equal vertical stripes, from left to right, red, white and blue.  If you have a line of N balls, each of which is randomly painted one of these colors, how can you sort the line so that all the red balls come first, followed by all the white balls, ending with all the blue balls together at the end?  You have to sort the array in place, and you are only allowed to look at each ball once. (Inspecting the color of a ball is a very expensive operation on the processor we are using, and we have very little RAM beyond the amount needed to hold the array representing the balls).

It's that last pair of constraints that make the problem so hard. If you are only allowed one look at a ball, that seems to imply that you must move the ball to its correct segment in the array as soon as you examine its color.  But you don't know how long each segment is (the balls are colored at random, and you don't know how many there are of each color).   If the first ball you see is white, where do you put it in the array?

I'm embarrassed to admit that when I first saw this problem, I could not see a way to solve it.   In practice, there's an easy way to finesse (cheat on) problems like this in computer science - simply apply the old rule of "add one more level of indirection".   Whip through the array, look at each ball to get the color, and keep a count of the number of balls of each color.  If you have R red balls, W white balls, and B blue balls, overwrite the array so the first R items are red, the next W are white, and the last (N- R+W) balls are blue.   Alas, this is cheating because you lose the original data, which (we presume) contains additional information beyond ball color.   At this point, novices often exclaim "use recursion!" and that is a fine idea, in theory.  

Recursive algorithms have three parts: a part that solves a little bit of the problem, making it slightly smaller; a "test condition" to check if the problem has now been completely solved; and a recursive call to execute the algorithm on the now slightly-smaller problem.   But how can that be applied here?   I'll wait...   The problem is that we don't yet have an algorithm to solve any part of the problem, not even a little bit of it.

Most developers that I know, want the chance to try to solve the Dutch National Flag problem for themselves, so I will provide the answer to the coding challenge in a future blog post.  In the meantime, here are a couple of  hints, in ROT 13 which can be decoded at https://rot13.com/.

Hint 1:   unir gur gbc tebhc tebj qbja sebz gur gbc bs gur neenl, gur obggbz tebhc tebj hc sebz gur obggbz, naq xrrc gur zvqqyr tebhc whfg nobir gur obggbz.
Hint 2:  (for those who just want to try coding the algorithm I give): Xrrc 3 vaqrkrf: gur obggbz bs gur gbc tebhc, gur gbc bs gur obggbz tebhc, naq gur gbc bs gur zvqqyr tebhc. Ryrzragf gung ner lrg gb or fbegrq snyy orgjrra gur zvqqyr naq gur gbc tebhc.Ng rnpu fgrc, rknzvar gur ryrzrag vzzrqvngryl nobir gur zvqqyr cbvagre. Vs gung onyy orybatf gb gur gbc tebhc, fjnc vg jvgu gur ryrzrag whfg orybj gur gbc. Vs vg orybatf va gur obggbz, fjnc vg jvgu gur ryrzrag whfg nobir gur obggbz. Vs vg vf va gur zvqqyr, yrnir vg. Hcqngr gur nccebcevngr vaqrk.  Evafr naq ercrng.