An algorithm to sort an array in linear time

Maintain two pointers: a red pointer pointing to 0 initially and a blue pointer pointing to the last element of array.

Now scan the array from left to right using the Examine function.

• Every time you encounter a red element, swap it (using the Swap function) with the current red pointer and increment the red pointer.
• Similarly, every time you encounter a blue element, swap it with the current blue pointer and decrement the blue pointer.
• Increment the current pointer when you encounter a white element.
• Stop when your current pointer crosses the blue pointer.

Now the array should be sorted as you want.

This is the Dutch National Flag Problem.

This is actually a very famous problem put forward by Dijkstra, known as the Dutch national flag problem.

The Wikipedia linked above gives a pretty decent account of how to approach this and other such problems.

A 3 way quick-sort may be applied to sole this as well. This presentation should give you a pretty good idea how to do so (the related content starts at page 37). Also, it does work in O(n) since the number of distinct keys is a constant, 3 (as stated on page 43).

This isn't really a sorting problem; it's a grouping problem.

Iterate through the list, counting the number of red, white, and blue elements. Now you know the exact structure of your solution, e.g.:

XXXXYYYYZZZZZZZZZ

Where X is red, Y is white, and Z is blue.

Now create three pointers: one at the location of the beginning of X, one at the beginning of Y, and one at the beginning of the Z in A.

Advance each pointer until it is at first element in its set that is wrong. For instance, if this is A:

XYXXYYXYZZZZZZZZZ

I

We would advance I, the X pointer, to the second position (index 1), because that element is out of place.

If you do that for each pointer, you know that each of the three pointers is pointing to an element out of place. Then iterate through the list. Whenever you find an element out of place, swap it with its corresponding pointer, i.e. if you find an X in the Ys, swap it with its Y pointer, and then increment that pointer (Y) until it is pointing to something out of place again.

Continue until the array is sorted.

Since you iterate through the list once (n ops) to get the structure and then each pointer at most will iterate through the list once (4 pointers → 4n), your total max runtime will be 5n which is O(n).

A very simple linear time algorithm is:

1. Loop once through the array and find the counts of reds, whites and blues as rcount, wcount, bcount.

2. Have three counters starting at 0, rcount, (rcount + wcount). Call them rcounter, wcounter and bcounter.

3. For each counter, increment until you get to a color that is not the right one for that range

4. Starting from 0, whenever you encounter a color: a. if the color is red and (counter < rcount), increment rcount and continue (likewise for white and blue depending on range) b. if the color is white, swap with wcounter and wcounter++ c. if the color is blue, swap with bcounter and bcounter++

When the loop ends you have your array.

I have gone through the Skiena book and saw this problem, too and here is my solution.

#include <stdio.h>

//swap the ith element of A with the jth element.
void swap(char arr[], int i, int j) {
    char temp;
    temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
    return;
}

int partition_color(char arr[], int low, int high, char color)
{
    int i;          // counter
    char p;          // pivot element
    int firsthing; // divider position for pivot

    p = color;          // choose the pivot element
    firsthing = high; // divider position for pivot element

    for (i = low; i < firsthing; i++) {
        if (arr[i] == color) {
            swap(arr, i, firsthing);
            firsthing--;
        }
    }

    return(firsthing);
}

void red_white_blue_sorting(char arr[], int n) {
    int pos;
    pos = partition_color(arr, 0, n, 'b');
    partition_color(arr, 0, pos, 'w');
    return;
}

int main() {

    char arr[] = {'r', 'b', 'r', 'w', 'b', 'w', 'b', 'r', 'r'};
    int n = sizeof(arr) / sizeof(arr[0]);

    red_white_blue_sorting(arr, n);
    for (int i = 0; i < n; i++)
        printf("%c ", arr[i]);

    printf("\n");
    return(0);
}

I was going through the Skiena book and saw this problem.

I got a solution with O(2n):

Suppose A = [B,R,W,R,W,B]

1. First go through the array and partition pivoting B, so that, all the values that are R or W will be pushed to the front of the array.

Now A will be; ['R', 'W', 'R', 'W', 'B', 'B'] => O(n)

2. Again go through A, pivoting on W, so that all the values that are R will be pushed to the front of the array. We can ignore B as they are already in place.

Result: ['R', 'R', 'W', 'W', 'B', 'B'] => O(2n)

This is a linear solution.

Is this correct way?