
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)


const dutchNationalFlag = () => {
 
  /**
   * Return the name of the given number in this way:
   * 0 = Red
   * 1 = White
   * 2 = Blue
   * @param {!number} e
   */
  const name = e => e > 1 ? 'Blue' : e > 0 ? 'White' : 'Red';
 
  /**
   * Given an array of numbers return true if each number is bigger than
   * or the same as the previous
   * @param {!Array<!number>} arr
   */
  const isSorted = arr => arr.every((e,i) => e >= arr[Math.max(i-1, 0)]);
 
  /**
   * Generator that keeps yielding a random int between 0(inclusive) and
   * max(exclusive), up till n times, and then is done.
   * @param max
   * @param n
   */
  function* randomGen (max, n) {
    let i = 0;
    while (i < n) {
      i += 1;
      yield Math.floor(Math.random() * max);
    }
  }
 
  /**
   * An array of random integers between 0 and 3
   * @type {[!number]}
   */
  const mixedBalls = [...(randomGen(3, 22))];
 
  /**
   * Sort the given array into 3 sub-arrays and then concatenate those.
   */
  const sortedBalls = mixedBalls
    .reduce((p,c) => p[c].push(c) && p, [[],[],[]])
    .reduce((p,c) => p.concat(c), []);
 
  /**
   * A verbatim implementation of the Wikipedia pseudo-code
   * @param {!Array<!number>} A
   * @param {!number} mid The value of the 'mid' number. In our case 1 as
   * low is 0 and high is 2
   */
  const dutchSort = (A, mid) => {
    let i = 0;
    let j = 0;
    let n = A.length - 1;
    while(j <= n) {
      if (A[j] < mid) {
        [A[i], A[j]] = [A[j], A[i]];
        i += 1;
        j += 1;
      } else if (A[j] > mid) {
        [A[j], A[n]] = [A[n], A[j]];
        n -= 1
      } else {
        j += 1;
      }
    }
  };
 
  console.log(`Mixed balls       : ${mixedBalls.map(name).join()}`);
  console.log(`Is sorted: ${isSorted(mixedBalls)}`);
 
  console.log(`Sorted balls      : ${sortedBalls.map(name).join()}`);
  console.log(`Is sorted: ${isSorted(sortedBalls)}`);
 
  // Only do the dutch sort now as it mutates the mixedBalls array in place.
  dutchSort(mixedBalls, 1);
  console.log(`Dutch Sorted balls: ${mixedBalls.map(name).join()}`);
  console.log(`Is sorted: ${isSorted(mixedBalls)}`);
};
dutchNationalFlag();
 