Understanding Counting Sort: Algorithm, Implementation, and Applications in C

Introduction

Sorting algorithms are a fundamental aspect of computer science, essential for organizing and manipulating data efficiently. Counting Sort is a distinctive non-comparative sorting algorithm that offers linear time complexity for specific types of input. This blog delves into the intricacies of Counting Sort, covering its algorithmic details, step-by-step logic, implementation in C, and its time and space complexities. By the end of this blog, you will have a comprehensive understanding of Counting Sort and its practical applications.

Algorithm Details

Counting Sort is particularly efficient for sorting integers when the range of the numbers (k) is not significantly larger than the number of elements (n). It works by counting the occurrences of each unique element in the input array, using these counts to determine the position of each element in the sorted output array.

Step-by-Step Logic

1. Find the Range: Determine the maximum element in the array to establish the range of the count array.
2. Initialize Count Array: Create a count array to store the frequency of each unique element.
3. Store Cumulative Counts: Modify the count array to store the cumulative count, which helps in placing elements directly into their correct position.
4. Build the Output Array: Use the count array to place elements into the correct position in the output array.
5. Copy Output to Original Array: Copy the sorted elements from the output array back to the original array.

Pseudo Code

CountingSort(arr):
    max = findMax(arr)
    count = array of zeros with length (max + 1)
    output = array of zeros with length (length of arr)

    # Store the count of each element
    for i = 0 to length(arr) - 1:
        count[arr[i]] += 1

    # Store the cumulative count
    for i = 1 to max:
        count[i] += count[i - 1]

    # Build the output array
    for i = length(arr) - 1 downto 0:
        output[count[arr[i]] - 1] = arr[i]
        count[arr[i]] -= 1

    # Copy the output array to arr
    for i = 0 to length(arr) - 1:
        arr[i] = output[i]

Explanation of Pseudo Code

1. CountingSort(arr):
   • max identifies the maximum value in the array to determine the range of the count array.
   • count array stores the frequency of each element.
   • The cumulative count in the count array determines the position of each element in the output array.
   • The output array is constructed by placing elements in their correct positions using the count array.
   • Finally, the sorted elements are copied back to the original array.

Implementation in C

Here is the implementation of Counting Sort in C.

#include <stdio.h>

// Function to find the maximum value in the array
int findMax(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++)
        if (arr[i] > max)
            max = arr[i];
    return max;
}

// Function to perform counting sort on the array
void CountingSort(int arr[], int n) {
    int max = findMax(arr, n);
    int count[max + 1];
    int output[n];

    // Initialize count array with all zeros
    for (int i = 0; i <= max; i++)
        count[i] = 0;

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

    // Store the cumulative count
    for (int i = 1; i <= max; i++)
        count[i] += count[i - 1];

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

    // Copy the output array to arr, so that arr now contains sorted elements
    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");
}

// Driver program to test above functions
int main() {
    int arr[] = {4, 2, 2, 8, 3, 3, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    CountingSort(arr, n);
    printf("Sorted array is: \n");
    printArray(arr, n);
    return 0;
}

Explanation of C Code

1. findMax(int arr[], int n):
   • Finds the maximum value in the array to determine the range of the count array.
2. CountingSort(int arr[], int n):
   • Initializes the count array to store the frequency of each element.
   • Modifies the count array to store the cumulative count.
   • Constructs the output array by placing elements in their correct positions.
   • Copies the sorted output array back to the original array.
3. printArray(int arr[], int n):
   • Utility function to print the elements of an array.
4. main():
   • The driver function to test the Counting Sort implementation with a sample array.

Time and Space Complexity

Understanding the complexity of Counting Sort is crucial for evaluating its performance.

Time Complexity

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

Space Complexity

• Counting Sort requires additional space for the count array and the output array.
• Space Complexity: O(n + k)

Usage of Counting Sort

Counting Sort is particularly useful in scenarios where the range of the elements (k) is not significantly larger than the number of elements (n). Common applications include:

• Sorting integers with a limited range: Particularly effective for small integers or when the range is known.
• Data normalization: Useful in preparing datasets for further analysis.
• Frequency counting: Efficiently counting occurrences of elements in a dataset.

Conclusion

Counting Sort is a highly efficient, non-comparative sorting algorithm that offers linear time complexity for specific types of input. Its unique approach of counting occurrences and using cumulative counts ensures that elements are sorted efficiently. With the detailed explanation, pseudo code, and C implementation provided in this blog, you should now have a solid understanding of Counting Sort and how to implement it in your projects.

By leveraging Counting Sort, you can achieve efficient and stable sorting for various applications, making it a valuable tool in your programming toolkit. Happy coding!

I hope you found this blog on Counting Sort informative and helpful. I welcome your feedback and suggestions for future posts. Please leave your comments below!