The reader is advised to read all the lessons (tutorials) in this full course, in the order presented.

Problem

Given an array A with n objects colored red, white, or blue; sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

Use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

You must solve this problem without using the library's sort function. Do it in O(n+m) time.

Example 1:
Input: A = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Example 2:
Input: A = [2,0,1]
Output: [0,1,2]

Constraints:

    n == A.length
    1 <= n <= 300
    A[i] is either 0, 1, or 2.

Strategy

- Produce the frequency-of-occurrences array, count.
- From the count array, read the frequency for the given element zero, and print those number of zeros; read the frequency for the given element 1, and print those number of 1's; and read the frequency for the given element 2, and print those number of 2's.

The Program

The program is (read through the code and comments):

#include <stdio.h>

void sortColors(int A[], int n, int m) { 
    int count[m+1];
    for (int i=0; i < m+1; i++)
        count[i] = 0;    //initializing count array

    //give frequencies to count array
    for (int i=0; i < n; i++)
        count[A[i]] = count[A[i]] + 1;
    
    //print
    for (int i=0; i < m+1; i++) {    //0 is an element in given array
        int frequency = count[i];
        for (int j=0; j < frequency; j++)
            printf("%i, ", i);
    }
    printf("\n");
}

int main(int argc, char **argv) 
{   
    int A1[] = {2,0,2,1,1,0};
    int n1 = sizeof(A1) / sizeof(A1[0]);    //length of given array
    int m1 = 0;    //for max number in A1
    for (int i=0; i < n1; i++)
        if (A1[i] > m1)
            m1 = A1[i];
    sortColors(A1, n1, m1);
    
    int A2[] = {2,0,1};
    int n2 = sizeof(A2) / sizeof(A2[0]);    //length of given array
    int m2 = 0;    //for max number in A1
    for (int i=0; i < n2; i++)
        if (A2[i] > m2)
            m2 = A2[i];
    sortColors(A2, n2, m2);
    return 0;
}

The output is:

    0, 0, 1, 1, 2, 2, 
    0, 1, 2, 

The official time complexity for the called function is O(n+m), with n for iterating over the given array and producing the count array, and m for for iterating over the count array and producing the sorted print. The time to initialize the count array to 0's is ignored.

The space complexity for the called function is O(n) for the given array.

Thanks for reading.