Partitioning the Dutch national flag


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:

  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);
});
    comments powered by Disqus