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 

Code Explanation

1. countingSort Function

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];
    }
}

• Purpose: Sorts the array in ascending order using the Counting Sort algorithm.
• How it works:
  1. Initialize the count array:
     • The count array is initialized with zeros. Its size is MAX_VALUE + 1 to accommodate all possible values in the input array.
  2. Count occurrences:
     • Iterate through the input array (arr) and count the occurrences of each element by incrementing the corresponding index in the count array.
  3. Cumulative sum:
     • Modify the count array to store the cumulative sum of counts. This helps in determining the correct position of each element in the sorted array.
  4. Reconstruct the sorted array:
     • Iterate through the input array in reverse order and place each element in its correct position in the sortedArray using the count array.
     • Decrement the count for each element after placing it in the sortedArray.
  5. Copy back to the original array:
     • Copy the sorted elements from sortedArray back to the original array (arr).

2. main Function

int main() {
    int arr[] = {5, 2, 7, 8, 4, 3, 1}; // Unsorted array
    int n = sizeof(arr) / sizeof(arr[0]); // Calculate array size
 
    printf("Original array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]); // Print original array
    }
    printf("\n");
 
    countingSort(arr, n); // Sort the array
 
    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]); // Print sorted array
    }
    printf("\n");
 
    return 0;
}

• Purpose: Drives the program.
• How it works:
  1. Declares and initializes an array arr with unsorted integers.
  2. Calculates the size of the array (n) using sizeof(arr) / sizeof(arr[0]).
  3. Prints the original array.
  4. Calls the countingSort function to sort the array.
  5. Prints the sorted array.

Key Points

1. Counting Sort:
   • Time Complexity: O(n + k), where n is the number of elements in the input array and k is the range of input (maximum value in the array).
   • Space Complexity: O(n + k).
   • It is a non-comparison-based sorting algorithm, making it efficient for sorting integers within a specific range.
2. How Counting Sort Works:
   • Counts the occurrences of each element.
   • Uses cumulative counts to determine the correct position of each element in the sorted array.
   • Reconstructs the sorted array using the counts.
3. Limitations:
   • Works only for non-negative integers.
   • Requires additional space for the count and sortedArray.