
The Dutch national flag is composed of three coloured bands in the order:

   red     (top)
   then white,   and
   lastly blue   (at the bottom). 


The problem posed by Edsger Dijkstra is:

Given a number of red, blue and white balls in random order, arrange them in the order of the colours in the Dutch national flag.
When the problem was first posed, Dijkstra then went on to successively refine a solution, minimising the number of swaps and the number of times the colour of a ball needed to determined and restricting the balls to end in an array, ...



Task
 Generate a randomized order of balls ensuring that they are not in the order of the Dutch national flag.
 Sort the balls in a way idiomatic to your language.
 Check the sorted balls are in the order of the Dutch national flag.


C.f.

 Dutch national flag problem
 Probabilistic analysis of algorithms for the Dutch national flag problem by Wei-Mei Chen. (pdf)


use AppleScript version "2.3.1" -- OS X 10.9 (Mavericks) or later — for these 'use' commands!
-- This script uses a customisable AppleScript sort available at <https://macscripter.net/viewtopic.php?pid=194430#p194430>.
-- It's assumed that scripters will know how and where to install it as a library.
use sorter : script "Custom Iterative Ternary Merge Sort"
 
on DutchNationalFlagProblem(numberOfBalls)
    -- A local "owner" for the potentially long 'balls' list. Speeds up references to its items and properties.
    script o
        property colours : {"red", "white", "blue"}
        -- Initialise the balls list with at least one instance of each colour — but not in Dutch flag order!
        property balls : reverse of my colours
    end script
 
    -- Randomly fill the list from the three colours to the required number of balls (min = 3).
    -- The task description doesn't say if there should be equal numbers of each colour, but it makes no difference to the solution.
    repeat numberOfBalls - 3 times
        set end of o's balls to some item of o's colours
    end repeat
    log o's balls -- Log the pre-sort order.
 
    -- Custom comparer for the sort. Decides whether or not ball 'a' should go after ball 'b'.
    script redsThenWhitesThenBlues
        on isGreater(a, b)
            return ((a is not equal to b) and ((a is "blue") or (b is "red")))
        end isGreater
    end script
    -- Sort items 1 thru -1 of the balls (ie. the whole list) using the above comparer.
    tell sorter to sort(o's balls, 1, -1, {comparer:redsThenWhitesThenBlues})
 
    -- Return the sorted list.
    return o's balls
end DutchNationalFlagProblem
 
DutchNationalFlagProblem(100)