Counting Sort

Counting Sort

Counting Sort is an integer sorting algorithm that operates by counting the number of occurrences of each unique element in the input array. It then uses this information to reconstruct a sorted array.

Here’s how Counting Sort works:

1. Counting Phase: Count the number of occurrences of each unique element in the input array and store these counts in an auxiliary array called the count array.
2. Prefix Sum Phase: Modify the count array to contain the cumulative sum of counts up to each index. This step helps determine the starting position of each element in the sorted array.
3. Sorting Phase: Iterate through the input array. For each element, find its position in the sorted array using the count array. Decrease the count of that element by one to handle duplicate elements.
4. Reconstruct Sorted Array: Use the count array to reconstruct the sorted array by placing each element in its correct position based on the counts.

Here’s a simple implementation of Counting Sort in C:

#include <stdio.h>

#define MAX_VALUE 10000 // Maximum value of elements in the array

void countingSort(int arr[], int n) {
    int count[MAX_VALUE + 1] = {0}; // Initialize count array with zeros
    int sortedArray[n]; // Create a temporary array to store sorted elements

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

    // Modify count array to contain cumulative sum
    for (int i = 1; i <= MAX_VALUE; i++) {
        count[i] += count[i - 1];
    }

    // Reconstruct the sorted array
    for (int i = n - 1; i >= 0; i--) {
        sortedArray[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] = sortedArray[i];
    }
}

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

    printf("Original array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    countingSort(arr, n);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

Output:

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

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 input values.

Here’s why:

• Counting Occurrences: In the counting phase, the algorithm iterates through the input array once to count the occurrences of each element. This step takes O(n) time.
• Constructing Count Array: The count array, which holds the occurrence count of each element, is initialized with a size equal to the range of input values. Hence, constructing this count array takes O(k) time.
• Prefix Sum and Sorting Phase: After counting, the algorithm iterates through the count array once to calculate the cumulative sum. This step also takes O(k) time. Then, it iterates through the input array once more to place elements in their correct positions in the sorted array. Since both these operations iterate through the input array only once, they collectively take O(n) time.

Therefore, the overall time complexity is O(n+k).