Detailed Explanation of Counting Sort Implementation in C

Counting sort is a non-comparison based sorting algorithm suitable for sorting integers, provided that the range of the elements to be sorted is known and relatively concentrated. Its core idea is to count the occurrences of each element and then reconstruct the ordered array based on these counts.

Basic Steps of Counting Sort

1. Determine the maximum and minimum values in the array to be sorted
2. Create a counting array with a size equal to the difference between the maximum and minimum values plus one
3. Count the occurrences of each element and store them in the counting array
4. Reconstruct the ordered array based on the counting array

Implementation Code

Header Files

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

Counting Sort Function

// Counting sort function
void countingSort(int arr[], int n) {
    if (n <= 0) {
        return;
    }
    // 1. Find the maximum and minimum values in the array
    int min = arr[0], max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] < min)
            min = arr[i];
        if (arr[i] > max)
            max = arr[i];
    }
    // 2. Calculate the size of the counting array and initialize it
    int range = max - min + 1;
    int* count = (int*)calloc(range, sizeof(int));
    if (count == NULL) {
        printf("Memory allocation failed\n");
        return;
    }
    // 3. Count the occurrences of each element
    for (int i = 0; i < n; i++) {
        count[arr[i] - min]++;
    }
    // 4. Reconstruct the original array based on the counting array
    int index = 0;
    for (int i = 0; i < range; i++) {
        while (count[i] > 0) {
            arr[index++] = i + min;
            count[i]--;
        }
    }
    // Free memory
    free(count);
}

Main Function

// Main function for testing
int main() {
    int arr[] = { 4, 2, 2, 8, 3, 3, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Array before sorting: ");
    printArray(arr, n);
    countingSort(arr, n);
    printf("Array after sorting: ");
    printArray(arr, n);
    return 0;
}

Output Function

// Print array
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

Code Analysis

Counting Sort Function (countingSort)：

• First, find the maximum and minimum values in the array to determine the data range
• Create a counting array based on the range to store the occurrences of each element
• Count the occurrences of each element
• Finally, reconstruct the original array based on the counting array to achieve sorting

The position count[i] stores the occurrences of the value (i+min) in the array to be sorted; if it is 0, it means it does not exist.

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

Traversing count can restore the array to be sorted in order

// 4. Reconstruct the original array based on the counting array
int index = 0;
for (int i = 0; i < range; i++) {
    while (count[i] > 0) {
        arr[index++] = i + min;
        count[i]--;
    }
}

Handling All Values：

// Test case including negative numbers
int arr2[] = { -5, 2, 0, -3, 1, 3, -2 };
int n2 = sizeof(arr2) / sizeof(arr2[0]);
printf("\nArray before sorting with negative numbers: ");
printArray(arr2, n2);
countingSort(arr2, n2);
printf("Array after sorting with negative numbers: ");
printArray(arr2, n2);

• The code maps all elements to a non-negative range by subtracting the minimum value
• This allows it to handle negative numbers correctly

Time Complexity：

• The time complexity is O(n + k), where n is the number of elements to be sorted and k is the range of the data
• This makes counting sort very efficient when the data range is small

Space Complexity：

• The space complexity is O(k), primarily used for storing the counting array

Advantages and Disadvantages of Counting Sort

Advantages：

• Fast speed with low time complexity
• Simple implementation
• Stable sorting algorithm

Disadvantages：

• Only suitable for sorting integers
• Can consume a lot of memory when the data range is large
• Not suitable for sparse data

Counting sort is particularly suitable for sorting scenarios with a small and concentrated range of integers, such as sorting student grades or ages. Counting sort is not suitable for sparse data, for example: { 1,5,99999} with a maximum and minimum difference of 99998. It would require a large amount of memory, and the length of the array traversed during reconstruction would be 99998.