Counting Sort

Counting Sort is a sorting algorithm that works well for sorting integers within a specific range. It doesn't rely on comparisons between elements like many other sorting algorithms; instead, it utilizes the actual values of the elements to determine their positions in the sorted output. Counting Sort is efficient when the range of input values is not significantly larger than the number of elements to be sorted.

Let's go through a dry run of the Counting Sort algorithm using the following unsorted array as an example:

Unsorted Array: [4, 2, 2, 8, 3, 3, 1]

1. **Find the Range**: Determine the range of input values by finding the minimum and maximum values in the array.

   - Min: 1

   - Max: 8

   - Range: 8 - 1 + 1 = 8

2. **Initialize Counting Array**: Create a counting array to store the frequency (count) of each value in the input array. The counting array will have a size equal to the range of input values.

   Counting Array: [0, 0, 0, 0, 0, 0, 0, 0, 0]

   

3. **Count Frequencies**: Traverse the input array and count the occurrences of each value. Increment the corresponding position in the counting array.

   Unsorted Array: [4, 2, 2, 8, 3, 3, 1]

   Counting Array: [0, 1, 2, 2, 1, 0, 0, 1, 1]

4. **Calculate Cumulative Counts**: Modify the counting array to hold the cumulative counts. This indicates how many elements are less than or equal to each value.

   Counting Array: [0, 1, 3, 5, 6, 6, 6, 7, 8]

5. **Create Sorted Output Array**: Initialize an output array to hold the sorted elements. Traverse the input array in reverse, place elements in the output array using the cumulative count as an index, and decrement the count.

   Unsorted Array: [4, 2, 2, 8, 3, 3, 1]

   Counting Array: [0, 1, 3, 5, 6, 6, 6, 7, 8]

   Sorted Output:   [0, 1, 1, 2, 2, 3, 3, 4, 8]

6. **Final Sorted Array**: The output array is the sorted version of the input array.

   Sorted Array: [1, 2, 2, 3, 3, 4, 8]

Counting Sort is efficient because it has a time complexity of O(n + k), where n is the number of elements in the input array and k is the range of input values. However, it's important to note that Counting Sort is not suitable for sorting non-integer values or when the range of values is much larger than the number of elements, as it can lead to excessive memory usage.

C Code

#include <stdio.h>

void countingSort(int arr[], int n) {

    int max = arr[0];

    int min = arr[0];

    // Find the range of input values

    for (int i = 1; i < n; i++) {

        if (arr[i] > max) {

            max = arr[i];

        }

        if (arr[i] < min) {

            min = arr[i];

        }

    }

    int range = max - min + 1;

    // Create and initialize the counting array

    int countingArray[range];

    for (int i = 0; i < range; i++) {

        countingArray[i] = 0;

    }

    // Count the occurrences of each value

    for (int i = 0; i < n; i++) {

        countingArray[arr[i] - min]++;

    }

    // Calculate cumulative counts

    for (int i = 1; i < range; i++) {

        countingArray[i] += countingArray[i - 1];

    }

    // Create the sorted output array

    int sortedArray[n];

    for (int i = n - 1; i >= 0; i--) {

        sortedArray[countingArray[arr[i] - min] - 1] = arr[i];

        countingArray[arr[i] - min]--;

    }

    // Copy the sorted array back to the original array

    for (int i = 0; i < n; i++) {

        arr[i] = sortedArray[i];

    }

}

int main() {

    int arr[] = {4, 2, 2, 8, 3, 3, 1};

    int n = sizeof(arr) / sizeof(int);

    countingSort(arr, n);

    printf("Sorted array: ");

    for (int i = 0; i < n; i++) {

        printf("%d ", arr[i]);

    }

    return 0;

}

Contact us for software training, education or development