Dutch Flag Problem In Ruby

Recently I did a code kata for a sorting problem. At the time I didn’t realize it but it’s a called the “Dutch Flag Problem” and Dijkstra came up with it back in 1976 in his book A Discipline of Programming.

The problem is as follows:

Given an array known to contain only the numbers 0, 1 and 2 sort it in O(n).

So for example if you had the input:

[0,1,1,0,2,1,2,0]


Then the output would be:

[0,0,0,1,1,1,2,2]


The time complexity requirement rules out the possibility of using an untuned general sort from most languages standard library (most sorts of that sort are O(n log n)).

There are actually 2 ways of solving the problem.

The first method of solving it is sort of cheating but is simpler. Just iterate the array and maintain a hash of (digit => count). This will get you the information you’re after but you didn’t really sort the data. (In a real world scenario this is probably sufficient though since you probably aren’t going to actually want to iterate the same digit N times if you know there are N of them in the array.)

The 2nd method of solving the problem is the more interesting one. Given that we have known constraints on the incoming data we can develop an algorithm specifically tuned for the situation. The problem becomes one of partitioning:

def sort(data)
return nil if !data

left = 0
mid = 0

while mid <= right
if suspect == 0
left += 1
mid += 1
elsif suspect == 2
right -= 1
else
mid += 1
end
end