Sort Colors

LeetCode Problem #75 (Medium)

Problem Statement

Given an array 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. Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:

You are not supposed to use the library's sort function for this problem.

Testcase

Example 1:

Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Prerequisite Knowledge

Counting Sort

Counting Sort is a sorting algorithm that is used to sort elements with duplicates in an array by counting the number of occurrences of each distinct element. An auxiliary array is used to store the count value of each unique element.

The sorting is performed by mapping the values in the auxiliary array as the index values of the distinct elements in the sorted output array.

Algorithm

Initialize count array with zeros.
Iterate from i to size_of_array and count the occurrence of each element in the count array.
Iterate from i to size_of_count and calculate and store the actual index values of the elements in the count array.
Iterate from i to size_of_array and insert the elements in the correct index position in the output array.
Copy the elements in the output array to the original array.

Algorithm

Counting Sort Approach

In this approach, we use two auxiliary arrays to store the count of each element and to build the sorted array, using a calculation of the relative position of the first occurrence of each new element with respect to the position of the last occurrence of the previous element.

1. Initialize a counter array to store the count of each element and an output array to store the sorted elements.

2. Iterate through the original array and increment the count of each encountered element, while unseen element remain 0.

3. Change the count array to reflect the actual index of each element in the sorted array by adding the count of the previous element.

4. Build the output array by iterating through the length of the count array.

   a. Store each element in the output array at the index determined by the index value of the element in the count array.

   b. Decrement the count array.

5. Copy the output array to the original array.

Time Complexity: O(n+k)

Illustration

Consider the array [2, 1, 1, 2, 0].

We create a count array to store the number of times each element occurs in the original array.

Count Array

count -> [1, 2, 2]
value ->  0  1  2

We must change each index in the count array to reflect the actual index position that the elements would take in the output array by considering the number of times the previous element occurs and storing the new element at the index immediately after the last occurrence of the previous element.

count[i] = current_index + count[i-1]

count[0] = 0 + 0 = Index 0
count[1] = 0 + 1 = Index 1
count[2] = 1 + 2 = Index 3

count -> [0, 1, 3]

Now, the count array contains the index value at which each element must be placed. Until a new index value is reached, the previous element's value will be repeated, thus effectively rendering that element the number of times that it has occurred in the original array.

Output Array

output[0] = 0 (0 begins at index 0)
output[1] = 1 (1 begins at index 1)
output[2] = 1
output[3] = 2 (2 begins at index 3)
output[4] = 2

output -> [0, 1, 1, 2, 2]

Code

void sortColors(vector<int>& nums) {
    int len = nums.size();
    int output[len], count[1000] = {0};
    // Accumulate count of each element
    for(int i = 0; i < len; i++) {
        count[nums[i]]++;
    }
    // Change count[i] such that it contains the actual index of each element in the sorted array
    for(int i = 1; i < 1000; i++) {
        count[i] += count[i-1];
    }
    // Build the output array using the index value from the count array and element value from the nums array
    for(int i = 0; i < len; i++) {
        output[count[nums[i]] - 1] = nums[i];
        count[nums[i]]--;
    }
    // Copy the output array to the original array
    for(int i = 0; i < len; i++) {
        nums[i] = output[i];
    }
}