24 Oct 2013. comments
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:
Then the output would be:
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 answer = data.dup return answer if answer.length <= 1 left = 0 mid = 0 right = answer.length - 1 while mid <= right suspect = answer[mid] if suspect == 0 answer[mid], answer[left] = answer[left], answer[mid] left += 1 mid += 1 elsif suspect == 2 answer[mid], answer[right] = answer[right], answer[mid] right -= 1 else mid += 1 end end answer end
We iterate through the array once and if the current element under inspection is a 0 then we kick it to the left just beyond where a 0 was last placed. Otherwise if it’s a 2 then kick it to the right just before where a 2 was last placed. In the end you get the partitioned data.