
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)


 
CLOSE DATABASES ALL
LOCAL lcCollate As String, i As Integer, n As Integer
lcCollate = SET("Collate")
SET COLLATE TO "Machine"
*!* Colours table
CREATE CURSOR colours (id I UNIQUE, colour V(5))
INSERT INTO colours VALUES (1, "Red")
INSERT INTO colours VALUES (2, "White")
INSERT INTO colours VALUES (3, "Blue")
*!* Balls table
CREATE CURSOR balls (colour I, rowid I AUTOINC)
INDEX ON colour TAG colour
SET ORDER TO 0
*!* Make sure there is at least 1 of each colour
INSERT INTO balls (colour) VALUES(3)
INSERT INTO balls (colour) VALUES(1)
INSERT INTO balls (colour) VALUES(2)
RAND(-1)	&& Initialise random number generator
n = 24
FOR i = 4 TO n
	INSERT INTO balls (colour) VALUES (RanInt())
ENDFOR
*!* Show unsorted
SELECT bb.rowid, cc.colour FROM colours cc JOIN balls bb ON cc.id = bb.colour  
*!* Select by correct order
SELECT bb.rowid, cc.colour FROM colours cc JOIN balls bb ON cc.id = bb.colour ;
ORDER BY cc.id INTO CURSOR dutchflag 
*!* Show sorted records
BROWSE NOMODIFY IN SCREEN 
SET COLLATE TO lcCollate
 
FUNCTION RanInt() As Integer
RETURN INT(3*RAND()) + 1
ENDFUNC
 