Understanding Counting Sort: An Easy Guide

Understanding Counting Sort: An Easy Guide

Sorting is a fundamental concept in computer science, and there are many sorting algorithms to choose from. One of the most efficient algorithms for sorting integers within a limited range is Counting Sort. In this blog, we will explore how Counting Sort works and write its implementation in C.

Counting Sort is a non-comparison-based sorting algorithm. Instead of comparing elements, it uses the frequency (or count) of each unique element in the array to determine their sorted position. It works best when:

  • The range of input values is not excessively large.

  • The input contains integers or data that can be mapped to integers (like characters).

Counting Sort is particularly efficient for scenarios where data falls within a predictable and narrow range, making it a great choice for specific use cases like sorting grades, ages, or digits of numbers.

Here are the steps for Counting Sort:

  1. Find the Range: Determine the maximum value in the array (this defines the range of the count array).

  2. Create the Count Array: Create an auxiliary array (count array) to store the frequency of each element.

  3. Cumulative Count: Update the count array so that each index contains the sum of its own count and all previous counts. This step helps determine the position of each element in the sorted array.

  4. Build the Output Array: Traverse the original array in reverse order to maintain stability and use the count array to place elements in their correct position in a new output array.

  5. Copy Back: Copy the sorted elements from the output array back to the original array.

  • Stability: Counting Sort is stable, meaning that it preserves the relative order of elements with the same value.

  • Space Complexity: The algorithm uses additional space for the count array and output array, making its space complexity O(n + k), where n is the size of the input array and k is the range of input values.

  • Time Complexity: The time complexity is O(n + k), making it very efficient for small ranges of k.

Here’s the code for Counting Sort in C:

#include <stdio.h>
#include <string.h>

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

    // Create and initialize the count array
    int count[max + 1];
    memset(count, 0, sizeof(count));

    // Count the occurrences of each element
    for (int i = 0; i < n; i++) {
        count[arr[i]]++;
    }

    // Update the count array to store cumulative counts
    for (int i = 1; i <= max; i++) {
        count[i] += count[i - 1];
    }

    // Create the output array
    int output[n];

    // Build the sorted output array
    for (int i = n - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }

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

// Utility function to print an array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

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

    printf("Original array: \n");
    printArray(arr, n);

    countingSort(arr, n);

    printf("\nSorted array: \n");
    printArray(arr, n);

    return 0;
}
  1. Finding the Maximum Value: The maximum value determines the size of the count array.

  2. Count Array:

    • The count array is initialized to zero.

    • Each index represents a value in the input array, and the value at that index represents the frequency of the element.

  3. Cumulative Count: This step ensures that each index in the count array contains the position of the last occurrence of the element in the sorted order.

  4. Building the Output Array: Traversing the input array in reverse ensures the stability of the algorithm.

  5. Copy Back: The sorted elements are copied back to the original array.

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

  1. Find the Range: Max value is 8.

  2. Count Array: After counting occurrences: [0, 1, 2, 2, 1, 0, 0, 0, 1]

  3. Cumulative Count: After cumulative count: [0, 1, 3, 5, 6, 6, 6, 6, 7]

  4. Output Array: Using the count array: [1, 2, 2, 3, 3, 4, 8]

  5. Final Result: Sorted array: [1, 2, 2, 3, 3, 4, 8]

  • Very fast for small ranges.

  • Simple to implement for integer or character data.

  • Inefficient for large ranges due to high space usage.

  • Cannot be used directly for non-integer data.

Counting Sort is a powerful algorithm when the range of input values is limited and predictable. It is fast and stable, making it an excellent choice for specific sorting tasks. However, for larger or more general cases, other sorting algorithms like Quick Sort or Merge Sort may be better suited.