Table of Contents
Counting Sort is an efficient sorting algorithm used for sorting integers within a specific range. It works by counting the number of occurrences of each value and then calculating the positions of each element in the sorted array. This method is particularly useful when the range of input data is not significantly larger than the number of elements to sort.
How Counting Sort Works
The algorithm begins by creating a count array that stores the frequency of each value in the input data. It then modifies this count array to contain the actual positions of each element in the sorted output. Finally, it builds the sorted array by placing elements at their correct positions based on the count array.
Calculation Example
Suppose we have the array: [4, 2, 2, 8, 3, 3, 1]. The range of values is from 1 to 8. The counting process results in a count array:
[0, 1, 2, 2, 1, 0, 0, 0, 1]
This indicates the frequency of each number. The algorithm then computes the cumulative counts to determine the positions:
[0, 1, 3, 5, 6, 6, 6, 6, 7]
Using these, the sorted array becomes: [1, 2, 2, 3, 3, 4, 8].
Application Scenarios
Counting Sort is suitable for scenarios where the input data consists of integers within a known, limited range. It is often used in:
- Sorting student grades (e.g., 0-100)
- Organizing data in frequency analysis
- Sorting small integers in embedded systems
- Implementing radix sort as a subroutine
Its efficiency depends on the size of the range relative to the number of elements. When the range is small, Counting Sort can outperform comparison-based algorithms like quicksort or mergesort.