Programming exercise: red-white-blue sorting

I’ve been practising coding on the whiteboard for job interviews. This is very different than coding in front of a computer which has a keyboard, a monitor, and a nice editing program that allows you to correct your mistakes and type repetitive text very quickly. I’m trying to keep my programs simple and short, and writing in a C-like pseudocode.

This exercise comes from Skiena’s The Algorithm Design Manual^[1]\(\).

You are given an array \(A\) of \(n\) elements, each of which is one of red, white, or blue. The only permitted operations on \(A\) are to examine an item at position \(i\) using Examine(i), and to swap two items at positions \(i\) and \(j\) using Swap(i,j). The problem is to sort the elements as efficiently as possible, such that the elements are in the order red, followed by white, then finally blue.

The trick to coding on a whiteboard is to first draw some simple visual examples, and use them to talk your interviewer (or yourself) through how the algorithm is supposed to work, before writing down any actual code. It’s very important that you have the algorithm you want to code before you start coding, because any editing other than very minor changes is basically impossible on a whiteboard.

The first thing to notice is that we can do better than the standard \(O(n\log n)\) sorting algorithms, since the number of different values for the elements is a small constant. My first thought was to make one pass of the array to count the number of red, white, and blue elements, one more pass to put all the red elements in front, and a final pass to put the white elements before the blue ones. While this algorithm is linear time, which is asymptotically the best you can do, with a little thought and a little bookkeeping, it’s possible to do everything in just one pass of the array.

The idea is as follows. Keep two “pointers”, say \(r\) and \(b\), which begin at the front and back respectively, and which keep track of the places where the next red and blue elements should go. Now sweep the array from front to back.

If the current position has a blue element, swap it to position \(b\). Now, we decrement \(b\), but we don’t advance the position of the sweep yet, because we might have just swapped in another blue element. This rule ensures that there are no blue elements behind us (i.e., towards the front of the array).

Dealing with a red element is a bit trickier, since both the \(r\) pointer and the sweep’s position are advancing. If we’re at the same position as the \(r\) pointer, there’s a contiguous block of red elements behind us, and we can simply increment \(r\) and move on to the next position. If we’re ahead of the \(r\) pointer, we can swap the red element to that position, and increment \(r\). Note that we can only ever swap in a white element, since we’ve guaranteed that there are no blue elements behind us, and \(r\) is always beyond the continguous block of known red elements at the front.

Finally, if the current position has a white element, we can just skip over it. If it’s in the wrong position, it’ll be dealt with later when we encounter the red element it needs to be swapped with.

The loop terminates when our sweep hits the contiguous block of blue elements at the back of \(A\), i.e., when \(pos > b\). For simplicity, we assume that \(n \geq 1\) (which we can always check for before we begin).

This is the algorithm I came up with on the whiteboard:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

int r, b, pos;
 
r = 0; b = n-1;
while(Examine(r) == 'R') { r++; }
while(Examine(b) == 'B') { b--; }
 
pos = r;
 
while( pos <= b ) {
    char val = Examine(pos);
    if( val == 'B' ) {
        Swap(b, pos);
        b--;
    } else if( val == 'R' ) {
        if( r < pos ) {
            Swap(r, pos);
        } else {
            pos++;
        }
        r++;
    } else if( val == 'W' ) {
        pos++;
    }
}

I’ve assumed that Examine(i) returns one of 'R', 'W', or 'B'. The \(pos\) variable keeps track of the position as I sweep the array from front to back. The two initial loops skip over any red elements at the front and any blue elements at the back of the array (these are not strictly necessary, but make things a bit faster in some cases). Each element is examined exactly once, for a total run time of \(n\), making this the most efficient algorithm possible.

– davinci 11847

Be Sociable, Share!

•