Yesterday’s post from Programming Praxis asks us to solve a problem known as the Dutch National Flag problem (attributed to Edsgar Dijkstra): sort an array of red, white and blue symbols so that all reds come together, followed by all whites, followed finally by all blues.
For once, the first algorithm to come to mind was actually the correct one. This doesn’t always happen quite so nicely, but it is pleasant when it does. The basic idea is similar to the in-place partition often used with quicksorts ((This is actually more of a partitioning problem than a sorting one)): Start with labels at the beginning and end of the array; advance the labels towards each other, swapping elements on the wrong side of the pivot.
In this case, there are three labels (one for each color), but that doesn’t actually change the algorithm much at all. Here are the basic steps:
- Start with three labels Lr = 0, Lw = 0, Lb = |data| - 1
- While Lw < Lb, check the element at Lw:
- Red: Swap Lr and Lr and increment Lr and Lw
- White: Increment Lw
- Blue: Swap Lw and Lb and decrement Lb
That’s all there is to it. Here’s how you might translate that into Racket:
(define (vector-swap! v i j)
(define temp (vector-ref v i))
(vector-set! v i (vector-ref v j))
(vector-set! v j temp))
(define (partition-flag! flag)
(let loop ([r 0] [w 0] [b (- (vector-length flag) 1)])
(cond
[(> w b) flag]
[(eq? (vector-ref flag w) 'red)
(vector-swap! flag r w)
(loop (+ r 1) (+ w 1) b)]
[(eq? (vector-ref flag w) 'white)
(loop r (+ w 1) b)]
[(eq? (vector-ref flag w) 'blue)
(vector-swap! flag w b)
(loop r w (- b 1))])))
Since the code is relative straight forward, I went ahead off the deep end and worked out a visualization that will run in your web browser. If everything works as it should, clicking ‘Run Demo’ below should show you exactly what happens when partitioning a 50-element vector.
Demo
jQuery(function($) {
// Context to draw with
var canvas = $('#canvas')[0];
var context = canvas.getContext('2d');
var progress = $('#progress');
// Various constants
var demo_size = 50;
var demo_step = 250;
var left_offset = canvas.width / 10;
var top_offset = canvas.height / 6;
var block_width = 4/5 * canvas.width / demo_size;
var block_height = 1/3 * canvas.height;
var label_width = 3;
var label_height = block_height / 3;
// Data for the simulation
var styles = new Array('red', 'white', 'blue');
var labels = new Array(0, 0, 0);
var data = new Array();
var tick = 0;
var comparisons = 0;
var swaps = 0;
// Logging function
function log(msg) {
progress.html(
'Step ' + tick + ':<br />' +
msg + '<br /><br />' +
'So far:<br />' +
comparisons + ' comparisons<br />' +
swaps + ' swaps<br />' +
demo_size + ' elements'
);
}
// Run the entire demo
function showDemo() {
// Generate a new set of data
data = new Array(demo_size);
for (var i = 0; i < data.length; i++) {
data[i] = Math.floor(Math.random() * 3);
}
// Reset the arrays to left, left, and right
labels = new Array(0, 0, data.length - 1);
// Clear progress and raw everything the first time
progress.text('');
draw();
// Run the update functions
comparisons = 0;
swaps = 0;
tick = 0;
function simStep() {
tick += 1;
if (step())
setTimeout(simStep, demo_step);
else
log("finished");
draw();
}
setTimeout(simStep, demo_step);
}
// Swap two data points
function swap(i, j) {
swaps += 1;
var temp = data[i];
data[i] = data[j];
data[j] = temp;
}
// Take a single step of the sorting function
function step() {
// Stop when the white and blue pointers cross
if (labels[1] > labels[2]) {
return false;
}
// On red: swap to red and increment red and white
else if (data[labels[1]] == 0) {
log('red, swap to red and increment red and white');
swap(labels[0], labels[1]);
labels[0] += 1;
labels[1] += 1;
}
// On white: increment white
else if (data[labels[1]] == 1) {
log('white, increment white');
labels[1] += 1;
}
// On blue: swap to blue and decrement blue
else if (data[labels[1]] == 2) {
log('blue, swap to blue and decrement blue');
swap(labels[1], labels[2]);
labels[2] -= 1;
}
// Done, signify that we took a step
comparisons += 1;
return true;
}
// Draw the blocks and labels
function draw() {
// Clear the screen
context.clearRect(0, 0, canvas.width, canvas.height);
// Draw blocks
context.lineWidth = 1;
context.strokeStyle = 'black';
for (var i = 0; i < data.length; i++) {
context.beginPath();
context.rect(
left_offset + i * block_width,
top_offset,
block_width,
block_height
);
context.fillStyle = styles[data[i]];
context.fill();
context.stroke();
}
// Draw labels
var center_x = 0, center_y = 0;
for (var i = 0; i < labels.length; i++) {
center_x = left_offset + labels[i] * block_width + block_width / 3;
center_y = 2 * top_offset + block_height + i * label_height;
context.beginPath();
context.rect(
center_x - label_width / 2,
center_y - label_height / 2,
label_width,
label_height
);
context.fillStyle = styles[i];
context.fill();
context.stroke();
}
}
$('#run').click(showDemo);
});