C++ Program To Implement Counting Sort

Counting sort is an efficient integer sorting algorithm that works by counting the occurrences of each distinct element in the input array. It then uses this count information to place each element into its correct sorted position.

In this article, you will learn how to implement Counting Sort in C++, understand its mechanism, and explore its applications.

Problem Statement

The problem is to sort an array of non-negative integers. Traditional comparison-based sorting algorithms like Quick Sort or Merge Sort have a lower bound of O(N log N) time complexity. For specific scenarios, particularly when the range of input numbers (k) is not significantly larger than the number of elements (N), a non-comparison sort like Counting Sort can offer better performance.

Example

Consider an unsorted array: [4, 2, 2, 8, 3, 3, 1]

The sorted output array would be: [1, 2, 2, 3, 3, 4, 8]

Background & Knowledge Prerequisites

To understand and implement Counting Sort, you should be familiar with:

• C++ Basics: Fundamental syntax, variables, data types, and control structures (loops, conditionals).
• Arrays: Declaring, initializing, accessing, and iterating through one-dimensional arrays.
• Dynamic Memory Allocation (Optional but useful): Understanding new and delete for creating arrays whose size is determined at runtime.
• Basic Sorting Concepts: An understanding of what sorting entails and why different algorithms exist.

Use Cases or Case Studies

Counting Sort is particularly useful in specific scenarios due to its linear time complexity:

• Sorting a fixed range of integers: When the numbers to be sorted are integers within a known, relatively small range (e.g., ages of students, pixel values 0-255).
• Radix Sort as a subroutine: Counting Sort is often used as a stable sorting subroutine in Radix Sort, which can sort larger numbers by processing digits individually.
• Data preparation for other algorithms: When an algorithm requires input data to be pre-sorted and the data fits Counting Sort's criteria.
• Ranking items: Determining the rank of items in a collection where items have integer scores.
• Frequency analysis: Counting the occurrences of items can be the first step in frequency analysis, and Counting Sort inherently does this.

Solution Approaches

Counting Sort is a unique algorithm. We'll explore its single, distinct approach by breaking down its steps into logical phases.

Approach 1: The Counting Sort Algorithm

Counting Sort sorts elements by first counting the number of occurrences of each distinct element and then using arithmetic on those counts to determine the positions of each element in the output sequence.

One-line summary: Create a frequency array for elements, adjust it to store cumulative counts, and then iterate backward through the original array to place elements in their correct sorted positions in an auxiliary output array.

// Counting Sort Implementation
#include <iostream>
#include <vector>
#include <algorithm> // Required for std::max_element

using namespace std;

void countingSort(vector<int>& arr) {
    if (arr.empty()) {
        return; // Nothing to sort
    }

    // Step 1: Find the maximum element in the input array
    // This determines the size of the count array.
    int max_val = *max_element(arr.begin(), arr.end());

    // Step 2: Create a count array to store frequency of each element
    // The size of count_array will be max_val + 1 to accommodate 0 to max_val.
    vector<int> count(max_val + 1, 0);

    // Step 3: Populate the count array
    // count[i] will store the number of occurrences of i in arr.
    for (int x : arr) {
        count[x]++;
    }

    // Step 4: Modify the count array to store cumulative counts
    // count[i] will now store the number of elements less than or equal to i.
    for (int i = 1; i <= max_val; i++) {
        count[i] += count[i - 1];
    }

    // Step 5: Create an output array to store the sorted elements
    // This array will have the same size as the input array.
    vector<int> output(arr.size());

    // Step 6: Iterate through the input array from right to left
    // Place each element into its correct sorted position in the output array.
    // Decrement the count for that element to handle duplicates correctly.
    for (int i = arr.size() - 1; i >= 0; i--) {
        // The correct position for arr[i] is count[arr[i]] - 1
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--; // Decrement count for stability and duplicate handling
    }

    // Step 7: Copy the sorted elements from the output array back to the original array
    arr = output;
}

int main() {
    // Step 1: Initialize an unsorted array
    vector<int> arr = {4, 2, 2, 8, 3, 3, 1};

    cout << "Original array: ";
    for (int x : arr) {
        cout << x << " ";
    }
    cout << endl;

    // Step 2: Call the countingSort function
    countingSort(arr);

    cout << "Sorted array: ";
    for (int x : arr) {
        cout << x << " ";
    }
    cout << endl;

    // Example with another array
    vector<int> arr2 = {10, 4, 1, 4, 2, 10, 7};
    cout << "\\nOriginal array 2: ";
    for (int x : arr2) {
        cout << x << " ";
    }
    cout << endl;
    countingSort(arr2);
    cout << "Sorted array 2: ";
    for (int x : arr2) {
        cout << x << " ";
    }
    cout << endl;

    return 0;
}

Run

Sample Output:

Original array: 4 2 2 8 3 3 1
Sorted array: 1 2 2 3 3 4 8

Original array 2: 10 4 1 4 2 10 7
Sorted array 2: 1 2 4 4 7 10 10

Stepwise Explanation:

1. Find Maximum Element: The first step is to determine the largest value in the input array. This value (let's call it max_val) is crucial because it dictates the size of our count array, which needs to store frequencies up to max_val.

• Example: For [4, 2, 2, 8, 3, 3, 1], max_val is 8.

1. Initialize Count Array: Create a count array of size max_val + 1 and initialize all its elements to zero. Each index i in count will represent the integer value i from the input array.

• Example: count array of size 9 (indices 0 to 8), all zeros.

1. Populate Count Array: Iterate through the input array. For each element x, increment count[x]. After this step, count[i] will hold the exact frequency of the number i in the original array.

• Example for [4, 2, 2, 8, 3, 3, 1]:
• count[1] becomes 1
• count[2] becomes 2
• count[3] becomes 2
• count[4] becomes 1
• count[8] becomes 1
• Other count indices remain 0.

1. Modify Count Array (Cumulative Sum): Iterate through the count array from the second element (index 1) up to max_val. For each count[i], add count[i-1] to it. After this, count[i] will store the total number of elements less than or equal to i. This directly gives us the final position of i in the sorted array (minus one, because array indices are 0-based).

• Example for count (after Step 3): [0, 1, 2, 2, 1, 0, 0, 0, 1]
• After cumulative sum:
• count[0] = 0
• count[1] = 1 (1 element <= 1)
• count[2] = 1 + 2 = 3 (3 elements <= 2)
• count[3] = 3 + 2 = 5 (5 elements <= 3)
• count[4] = 5 + 1 = 6 (6 elements <= 4)
• count[5] = 6 + 0 = 6
• count[6] = 6 + 0 = 6
• count[7] = 6 + 0 = 6
• count[8] = 6 + 1 = 7 (7 elements <= 8)
• New count array: [0, 1, 3, 5, 6, 6, 6, 6, 7]

1. Build Output Array: Create an output array of the same size as the input array. Iterate through the *original input array* from right to left (to ensure stability). For each element arr[i]:

• Its sorted position in the output array will be count[arr[i]] - 1.
• Place arr[i] into output[count[arr[i]] - 1].
• Decrement count[arr[i]] to handle duplicate elements correctly and ensure they occupy consecutive positions.
• Example for [4, 2, 2, 8, 3, 3, 1] and count [0, 1, 3, 5, 6, 6, 6, 6, 7]:
• Process arr[6] (1): output[count[1]-1] i.e., output[0] becomes 1. count[1] becomes 0.
• Process arr[5] (3): output[count[3]-1] i.e., output[4] becomes 3. count[3] becomes 4.
• Process arr[4] (3): output[count[3]-1] i.e., output[3] becomes 3. count[3] becomes 3.
• Process arr[3] (8): output[count[8]-1] i.e., output[6] becomes 8. count[8] becomes 6.
• Process arr[2] (2): output[count[2]-1] i.e., output[2] becomes 2. count[2] becomes 2.
• Process arr[1] (2): output[count[2]-1] i.e., output[1] becomes 2. count[2] becomes 1.
• Process arr[0] (4): output[count[4]-1] i.e., output[5] becomes 4. count[4] becomes 5.
• output array after this step: [1, 2, 2, 3, 3, 4, 8]

1. Copy Back: Copy the elements from the output array back into the original arr array.

Conclusion

Counting Sort is a linear-time sorting algorithm, making it very efficient for specific data distributions. Its time complexity is O(N + K), where N is the number of elements and K is the range of input values (max\_val - min\_val + 1). This contrasts with O(N log N) for comparison sorts. However, it requires additional space for the count and output arrays, making its space complexity O(N + K). It's best suited for sorting non-negative integers when the range of numbers is not excessively large compared to the number of elements.

Summary

• Counting Sort is an efficient, non-comparison based integer sorting algorithm.
• It operates in O(N + K) time, where N is the number of elements and K is the range of values.
• Its space complexity is O(N + K), requiring auxiliary arrays.
• The algorithm works by counting frequencies, converting to cumulative frequencies, and then placing elements into an output array based on these counts.
• It is particularly useful for sorting integers within a limited range and serves as a sub-routine for algorithms like Radix Sort.