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

Here is what I came up with. Instead of colors, I am using numbers.

// l  - index at which 0 should be inserted.
// m1 - index at which 1 should be inserted.
// m2 - index at which 2 should be inserted.
// h  - index at which 3 should be inserted.
l=m1=m2=0;
h=arr.length-1
while(m2 <= h) {
    if (arr[m2] == 0) {
        swap(arr, m2, l);
        l++;

        // m1 should be incremented if it is less than l as 1 can come after all
        // 0's
        //only.
        if (m1 < l) {
            m1++;
        }
        // Now why not always incrementing m2 as we used to do in 3 flag partition
        // while comparing with 0? Let's take an example here. Suppose arr[l]=1
        // and arr[m2]=0. So we swap arr[l] with arr[m2] with and increment l.
        // Now arr[m2] is equal to 1. But if arr[m1] is equal to 2 then we should
        // swap arr[m1] with arr[m2]. That's  why arr[m2] needs to be processed
        // again for the sake of arr[m1]. In any case, it should not be less than
        // l, so incrmenting.
        if(m2<l) {
            m2++;
        }       
    }
    // From here it is exactly same as 3 flag.
    else if(arr[m2]==1) {
        swap(arr, m1, m2)
        m1++;
        m2++;           
    }
    else if(arr[m2] ==2){
        m2++;
    }
    else {
        swap(arr, m2, h);
        h--;
    }           
}


}

Similarly we can write for five flags.

    l=m1=m2=m3=0;
    h= arr.length-1;
    while(m3 <= h) {
        if (arr[m3] == 0) {
            swap(arr, m3, l);
            l++;
            if (m1 < l) {
                m1++;
            }
            if(m2<l) {
                m2++;
            }
            if(m3<l) {
                m3++;
            }

        }
        else if(arr[m3]==1) {
            swap(arr, m1, m3);
            m1++;
            if(m2<m1) {
                m2++;
            }
            if(m3<m1) {
                m3++;
            }   

        }
        else if(arr[m3] ==2){
            swap(arr,m2,m3);
            m2++;
            m3++;
        }
        else if(arr[m3]==3) {
            m3++;
        }
        else {
            swap(arr, m3, h);
            h--;
        }   
    }