Dutch National Flag

March 5, 2013

A famous problem given by Edsgar Dijkstra is to sort an array of red, white and blue symbols so that all reds come together, followed by all whites, followed finally by all blues; it’s called the Dutch National Flag problem because the Dutch flag consists of three stripes with red at the top, blue at the bottom, and white in the middle. You are allowed to scan through the array only once, and the only operations permitted are to examine the color of the symbol at a given array location and to swap the symbols at two locations.

Your task is to write a program to perform the sort given above. When you are finished, you are welcome to read or run a suggested solution, or to post your solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

9 Responses to “Dutch National Flag”

  1. […] today’s Programming Praxis exercise, our goal is to implement a sorting algorithm for lists with three […]

  2. My Haskell solution (see http://bonsaicode.wordpress.com/2013/03/05/dutch-national-flag/ for a version with comments):

    import qualified Data.Vector as V
    
    swap :: Int -> Int -> V.Vector a -> V.Vector a
    swap i j a = a V.// [(i,a V.! j), (j,a V.! i)]
    
    flag :: V.Vector Char -> V.Vector Char
    flag xs = f (0, V.length xs - 1) xs 0 where
      f (r,b) a n = if n > b then a else case a V.! n of
        'R' -> f (r+1,b  ) (swap n r a) (n+1)
        'B' -> f (r,  b-1) (swap n b a) n
        _   -> f (r,  b  ) a            (n+1)
    
  3. seckcoder said

    My python solution here( https://github.com/seckcoder/geass/blob/master/dnf4.py ). Actually I implemented the Dutch National Flag Algorithm for 4 colors.

  4. jpverkamp said

    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.

  5. Jan Van lent said

    A Common Lisp implementation:

    (use-package :iterate)
    
    ;; (arotatef a i j k) -> (rotatef (aref a i) (aref a j) (aref a k))
    (defmacro arotatef (a &rest indices)
      `(rotatef ,@(mapcar (lambda (i) `(aref ,a ,i)) indices)))
    
    (defun rwb-sort (a)
      (iter (with next-red = 0) (with next-white = 0) (with next-blue = 0)
            (for x in-vector a)
            (ecase x
              (red (arotatef a next-blue next-white next-red)
                   (incf next-red) (incf next-white) (incf next-blue))
              (white (arotatef a next-blue next-white)
                     (incf next-white) (incf next-blue))
              (blue (incf next-blue)))))
    
    (let ((rwb '(red white blue)))
      (defun random-rwb ()
        (elt rwb (random 3))))
    
    (defun random-rwb-array (n)
      (iter (repeat n)
            (collect (random-rwb) :result-type 'vector))))
    
    (defun test (n)
      (let ((a (random-rwb-array n)))
        (rwb-sort a)
        a))
    
    
  6. My version in python without peaking at the solution.  For some reason, I had the idea of starting in the middle.
    
    def swap(arr, i, j):
        arr[i], arr[j] = arr[j], arr[i]
        
    def dutch_flag(x):
        '''
        >>> dutch_flag (['b', 'r', 'r', 'w', 'r', 'w', 'b', 'w', 'w', 'r'])
        ['r', 'r', 'r', 'r', 'w', 'w', 'w', 'w', 'b', 'b']
        '''
        l, u = 0, len(x) - 1
        m1 = (u + l) / 2
        m2 = (u + l) / 2
    
        while m1 >= l:
            if x[m1] == 'r':
                swap(x, m1, l)
                l = l + 1
            elif x[m1] == 'b':
                swap(x, m1, u)
                u = u - 1
            elif x[m1] == 'w':
                m1 = m1 - 1
    
        while m2 <= u:
            if x[m2] == 'r':
                swap(x, m2, l)
                l = l + 1
            elif x[m2] == 'b':
                swap(x, m2, u)
                u = u - 1
            elif x[m2] == 'w':
                m2 = m2 + 1
    
        return x
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 643 other followers

%d bloggers like this: