Partitioning the Dutch national flag

Posted

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 quicksorts1: 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:

  1. Start with three labels Lr = 0, Lw = 0, Lb = |data| – 1
  2. 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);
});
  1. This is actually more of a partitioning problem than a sorting one [↩]
← All →
← By category →

Leave a Reply