How To Do Counting Sort in C++

Introduction

Counting Sort is a non-comparison-based sorting algorithm that counts the occurrences of each distinct element in an array. It is particularly efficient for sorting integers when the range of values is known and relatively small. Unlike comparison-based algorithms like QuickSort or MergeSort, Counting Sort uses a count array to keep track of the frequency of each value in the input array and then arranges the elements in sorted order.

This post will explore how to implement Counting Sort in C++, discuss its time and space complexity, and walk through an example.

Time Complexity

• Best, Worst, and Average Case: O(n + k), where n is the number of elements in the array and k is the range of the input values.

Space Complexity

• Space Complexity: O(n + k), as it requires extra space to store the count array and output array.

Pseudocode for Counting Sort

function countingSort(arr):
    n = length(arr)
    
    # Step 1: Find the maximum value in the array
    maxValue = max(arr)
    
    # Step 2: Create a count array to store the count of each element
    count = array of size (maxValue + 1), initialized to 0
    
    # Step 3: Store the count of each element
    for i from 0 to n-1:
        count[arr[i]] += 1
    
    # Step 4: Accumulate the counts
    for i from 1 to maxValue:
        count[i] += count[i-1]
    
    # Step 5: Create an output array to store the sorted order
    output = array of size n
    
    # Step 6: Place elements into the output array based on the count array
    for i from n-1 to 0:
        output[count[arr[i]] - 1] = arr[i]
        count[arr[i]] -= 1
    
    # Step 7: Copy the output array back to the original array
    for i from 0 to n-1:
        arr[i] = output[i]

Explanation of Each Step in Counting Sort Pseudocode

Step 1: Find Maximum Value

We begin by identifying the maximum value in the array. This value determines the size of the count array. For example, if the maximum value is 8, we need a count array of size 9 (to include indices from 0 to 8).

Step 2: Create the Count Array

The count array stores the frequency of each element in the input array. Its size is based on the maximum value of the array, and all values are initialized to 0.

Step 3: Count the Elements

We then iterate through the input array and increment the corresponding index in the count array for each element in the input.

Step 4: Accumulate the Counts

Next, we accumulate the counts to determine the positions of elements in the sorted array. The count array will now contain the cumulative count of elements up to that point, determining where each element belongs.

Step 5: Create Output Array

We create an output array of the same size as the input array. This array will store the elements in sorted order.

Step 6: Place Elements in Sorted Order

We iterate through the input array in reverse, using the count array to determine the correct position of each element in the sorted array.

Step 7: Copy Output to Input

Finally, we copy the contents of the output array back into the original array, resulting in a sorted array.

C++ Implementation of Counting Sort

Here’s the complete C++ code for Counting Sort:

#include <iostream>
#include <vector>
using namespace std;

void countingSort(int arr[], int n) {
    // Step 1: Find the maximum value in the array
    int maxValue = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > maxValue) {
            maxValue = arr[i];
        }
    }

    // Step 2: Create a count array to store the frequency of each element
    vector<int> count(maxValue + 1, 0);

    // Step 3: Store the count of each element
    for (int i = 0; i < n; i++) {
        count[arr[i]]++;
    }

    // Step 4: Accumulate the count array
    for (int i = 1; i <= maxValue; i++) {
        count[i] += count[i - 1];
    }

    // Step 5: Create an output array to store the sorted elements
    vector<int> output(n);

    // Step 6: Place the elements into the output array based on count
    for (int i = n - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }

    // Step 7: Copy the output array back to the original array
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

// Function to print an array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {4, 2, 2, 8, 3, 3, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array: ";
    printArray(arr, n);

    countingSort(arr, n);

    cout << "Sorted array: ";
    printArray(arr, n);

    return 0;
}

Output:

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

Step-by-step Walkthrough: Counting Sort

Consider the input array:

{4, 2, 2, 8, 3, 3, 1}

Step 1: Find Maximum Value

The first step is to find the maximum value in the array. This value will determine the size of the count array. In this case, the maximum value is 8, so the count array will have a size of 9 (to accommodate values from 0 to 8).

Step 2: Create and Initialize the Count Array

Next, we create a count array of size maxValue + 1 = 9, and initialize all elements to 0. The count array will be used to store the frequency of each element in the input array.

Initially, the count array looks like this:

count[] = {0, 0, 0, 0, 0, 0, 0, 0, 0}

Step 3: Count the Frequency of Each Element

We then iterate through the input array and increment the corresponding index in the count array for each element.

• For the first element 4, increment count[4]:
  count[] = {0, 0, 0, 0, 1, 0, 0, 0, 0}
• For the second element 2, increment count[2]:
  count[] = {0, 0, 1, 0, 1, 0, 0, 0, 0}
• For the third element 2, increment count[2] again:
  count[] = {0, 0, 2, 0, 1, 0, 0, 0, 0}
• For the fourth element 8, increment count[8]:
  count[] = {0, 0, 2, 0, 1, 0, 0, 0, 1}
• For the fifth element 3, increment count[3]:
  count[] = {0, 0, 2, 1, 1, 0, 0, 0, 1}
• For the sixth element 3, increment count[3] again:
  count[] = {0, 0, 2, 2, 1, 0, 0, 0, 1}
• For the seventh element 1, increment count[1]:
  count[] = {0, 1, 2, 2, 1, 0, 0, 0, 1}

Now, the count array reflects the number of occurrences of each element in the input array.

Step 4: Accumulate the Counts

Next, we accumulate the counts in the count array to determine the positions of the elements in the sorted array. This step ensures that the count array reflects the position of each element in the sorted order.

• Accumulate count[1] with count[0] (no change to count[1]):
  count[] = {0, 1, 2, 2, 1, 0, 0, 0, 1}
• Accumulate count[2] with count[1]:
  count[] = {0, 1, 3, 2, 1, 0, 0, 0, 1}
• Accumulate count[3] with count[2]:
  count[] = {0, 1, 3, 5, 1, 0, 0, 0, 1}
• Accumulate count[4] with count[3]:
  count[] = {0, 1, 3, 5, 6, 0, 0, 0, 1}
• Accumulate count[5] with count[4]:
  count[] = {0, 1, 3, 5, 6, 6, 0, 0, 1}
• Accumulate count[6] with count[5]:
  count[] = {0, 1, 3, 5, 6, 6, 6, 0, 1}
• Accumulate count[7] with count[6]:
  count[] = {0, 1, 3, 5, 6, 6, 6, 6, 1}
• Accumulate count[8] with count[7]:
  count[] = {0, 1, 3, 5, 6, 6, 6, 6, 7}

The count array now reflects the positions of the elements in the sorted order.

Step 5: Place Elements in the Output Array

Now we place the elements from the input array into their correct positions in the output array using the cumulative counts from the count array.

We iterate through the input array backwards to maintain stability (i.e., to ensure that elements with the same value maintain their relative order):

• Starting from the last element (1), place it in the position count[1] - 1 = 0 in the output array:
  output[] = {1, _, _, _, _, _, _}
count[] = {0, 0, 3, 5, 6, 6, 6, 6, 7}
• For the next element (3), place it in the position count[3] - 1 = 4:
  output[] = {1, _, _, _, 3, _, _}
count[] = {0, 0, 3, 4, 6, 6, 6, 6, 7}
• For the next element (3), place it in the position count[3] - 1 = 3:
  output[] = {1, _, _, 3, 3, _, _}
count[] = {0, 0, 3, 3, 6, 6, 6, 6, 7}
• For the next element (8), place it in the position count[8] - 1 = 6:
  output[] = {1, _, _, 3, 3, _, 8}
count[] = {0, 0, 3, 3, 6, 6, 6, 6, 6}
• For the next element (2), place it in the position count[2] - 1 = 2:
  output[] = {1, _, 2, 3, 3, _, 8}
count[] = {0, 0, 2, 3, 6, 6, 6, 6, 6}
• For the next element (2), place it in the position count[2] - 1 = 1:
  output[] = {1, 2, 2, 3, 3, _, 8}
count[] = {0, 0, 1, 3, 6, 6, 6, 6, 6}
• For the last element (4), place it in the position count[4] - 1 = 5:
  output[] = {1, 2, 2, 3, 3, 4, 8}
count[] = {0, 0, 1, 3, 5, 6, 6, 6, 6}

Step 6: Copy Output to Original Array

Finally, copy the sorted elements from the output array back into the original array:

arr[] = {1, 2, 2, 3, 3, 4, 8}

Advantages of Counting Sort

• Efficient for small ranges: Counting Sort is ideal when the range of the input values is small relative to the number of elements.
• Stable sorting: Counting Sort preserves the relative order of equal elements.

Limitations of Counting Sort

• Inefficient for large ranges: When the range of values is large compared to the number of elements, Counting Sort becomes inefficient regarding space usage.

Conclusion

Counting Sort excels in sorting integers within a limited range, boasting linear time complexity O(n + k). It outperforms comparison-based algorithms when k (value range) isn’t significantly larger than n (number of elements). It’s ideal for discrete data like ages or grades but less suitable for large ranges or non-integer data. Its niche effectiveness highlights the importance of selecting appropriate algorithms based on data properties, encouraging developers to balance time complexity, space usage, and data specificity in their sorting choices.

Congratulations on reading to the end of this tutorial!

Read the following articles to learn how to implement Counting Sort:

In Python – How to do Counting Sort in Python

In JavaScript – How To Do Counting Sort in JavaScript

Have fun and happy researching!