SESO45 - Editorial

editorial
, ,
1

Problem Link

Counting Sort is a non-comparative sorting algorithm that sorts integers in linear time, given a fixed range of integer values. Unlike comparison-based algorithms such as Quick Sort or Merge Sort, Counting Sort leverages the distribution of values within the input array to achieve its efficiency. This makes it particularly useful for sorting arrays with a limited range of integer values.

Approach

Counting Sort works by counting the occurrences of each unique value in the input array and then using this information to place each value in its correct position in the sorted array. The approach can be broken down into the following steps:

  1. Initialization:

    • First, the algorithm identifies the maximum value (max_val) in the array. This value determines the size of the counting array, count, which tracks the frequency of each value in the input array.

  2. Counting Occurrences:

    • The algorithm then iterates over the input array and increments the corresponding index in the count array for each value encountered. The count array essentially records the number of times each value appears in the input array.

  3. Reconstructing the Sorted Array:

    • Finally, the algorithm iterates through the count array and reconstructs the sorted array. For each value in the count array with a non-zero count, the value is placed in the output array in the correct order based on its frequency.

Code Explanation

void countingSort(vector<int>& arr) {
    if (arr.empty()) return;  // Edge case: If the array is empty, there's nothing to sort

    // Find the maximum value in the array
    int max_val = *max_element(arr.begin(), arr.end());
    
    // Create a count array to store the frequency of each value
    vector<int> count(max_val + 1, 0);

    // Count the occurrences of each value in the array
    for (int num : arr) {
        count[num]++;
    }

    // Reconstruct the sorted array using the count array
    int sorted_index = 0;
    for (int i = 0; i <= max_val; ++i) {
        while (count[i] > 0) {
            arr[sorted_index++] = i;
            count[i]--;
        }
    }
}

How It Works

  • Counting Occurrences: The core idea of Counting Sort is to count the number of occurrences of each integer in the input array. This is done using the count array, where the index represents the integer value, and the value at each index represents the frequency of that integer in the input array.

  • Reconstructing the Array: After counting the occurrences, the algorithm reconstructs the sorted array by iterating through the count array. For each index i in the count array, if count[i] is greater than zero, i is placed into the sorted array as many times as count[i] indicates.

Complexity Analysis

  • Time Complexity: The time complexity of Counting Sort is O(n + k), where n is the number of elements in the input array, and k is the range of the input (i.e., the difference between the maximum and minimum values). This makes Counting Sort highly efficient for cases where k is not significantly larger than n.

  • Space Complexity: The space complexity of Counting Sort is O(k), where k is the range of the input values. This space is used to store the count array. Additionally, the space for the output array is O(n), but since the sorting is done in-place in this implementation, the extra space required is mainly for the count array.