Dutch National Flag
March 5, 2013
We begin with the examine
and swap
functions:
(define examine vector-ref)
(define (swap! xs p1 p2)
(let ((t (vector-ref xs p1)))
(vector-set! xs p1 (vector-ref xs p2))
(vector-set! xs p2 t))
xs)
Although it’s usually stated as a sorting problem, this is actually a partitioning problem. The usual solution is to maintain three pointers: a red pointer that initially points to the first location in the array, a white pointer that initially points to the first location in the array, and a blue pointer that initially points to the last location in the array. Then the array is scanned from left to right. Each time you encounter a red element, swap it with the current red pointer and increment the red and white pointers. Each time you encounter a blue symbol, swap it with the current blue pointer and decrement the blue pointer. Each time you encounter a white symbol, leave it where it is and increment the white pointer. The scan stops when the white pointer crosses the blue pointer, at which point the arrays is partitioned as requested:
(define (dutch-national-flag xs)
(let loop ((r 0) (w 0) (b (- (vector-length xs) 1)))
(if (< b w) xs
(case (examine xs w)
((#\R) (set! xs (swap! xs r w))
(loop (+ r 1) (+ w 1) b))
((#\W) (loop r (+ w 1) b))
((#\B) (set! xs (swap! xs b w))
(loop r w (- b 1)))))))
Here’s an example, augmented with the values at each step of the loop so you can see how the pointers track:
> (dutch-national-flag #(#\B #\W #\B #\R #\W #\R #\B))
0 0 6 #(B W B R W R B)
0 0 5 #(B W B R W R B)
0 0 4 #(R W B R W B B)
1 1 4 #(R W B R W B B)
1 2 4 #(R W B R W B B)
1 2 3 #(R W W R B B B)
1 3 3 #(R W W R B B B)
2 4 3 #(R R W W B B B)
#(R R W W B B B)
This is exactly the same algorithm as the “fat pivot” partition that is sometimes used in quicksort, which brings together all the array elements equal to the pivot instead of leaving them in place on one side or the other; the same algorithm is also used in ternary search tries. You can run the program at http://programmingpraxis.codepad.org/0UFUJWc0.
The original source of the exercise is Dijkstra’s book A Discipline of Programming, published by Prentice Hall in 1976.
[…] today’s Programming Praxis exercise, our goal is to implement a sorting algorithm for lists with three […]
My Haskell solution (see http://bonsaicode.wordpress.com/2013/03/05/dutch-national-flag/ for a version with comments):
[…] Question is from here: […]
My java solution here.
My python solution here( https://github.com/seckcoder/geass/blob/master/dnf4.py ). Actually I implemented the Dutch National Flag Algorithm for 4 colors.
[…] Pages: 1 2 […]
Here’s mine: Partitioning the Dutch national flag
This time, I have both a Racket version and a JavaScript version. The JavaScript has an HTML5 canvas visualizer which was pretty neat to write. It will show the blocks as it sorts, along with the three labels. Let me know if you have any problems running it, I haven’t tested it on anything but Win7/Chrome.
A Common Lisp implementation:
Dijkstra had really nothing better to do (not like me :-p).
Clojure/Script (try online at http://clojurescript.net/).
Tests:
=> (sort-flag [:blue :red :white])
[:red :white :blue]
=> (sort-flag [:blue :red :white :red :blue :white :blue :red])
[:red :red :red :white :white :blue :blue :blue]
=> (sort-flag [:white :blue :red :white :red :blue :white :blue :red])
[:red :red :red :white :white :white :blue :blue :blue]
=> (sort-flag [:white :blue :red :white :red :blue :white :blue :red :white])
[:red :red :red :white :white :white :white :blue :blue :blue]