Mauritus national flag problem

Question

I've made a solution for the Dutch national flag problem already.

But this time, I want to try something more difficult: the Mauritus national flag problem - 4 colours, instead of 3. Any suggestions for an effective algorithm?

Basically, The Mauritius National Flag Problem focuses on how you would be able to sort the given list of pairs based on the order of colors in the Mauritius National Flag (Red, Blue, Yellow, Green). And the numbers must be sorted in ascending order too.

Scheme Programming Sample Input:

( (R . 3) (G . 6) (Y . 1) (B . 2) (Y . 7) (G . 3) (R . 1) (B . 8) )

Output:

( (R . 1) (R . 3) (B . 2) (B . 8) (Y . 1) (Y . 7) (G . 3) (G . 6) )

Answer 1

This is just like the Dutch national flag problem, but we have four colors. Essentially the same strategy applies. Assume we have (where ^ represents the point being scanned).

  RRRRBBB???????????YYYYGGGG
         ^

and we scan a

1. red, then we swap the first blue with the current node
2. BLUE we do nothing
3. yellow we swap with the last ?
4. Green we swap the last yellow with the last ? Then the current node with the swapped ?

So we need to keep track or one more pointer than usual.

We need to keep track of the first blue, the first ?, the last ?, the last Y

In general, the same strategy works for any number of colors, but an increasing numbers of swaps are needed.