Welcome to TheCodingCollege.com! In this article, we’ll analyze the time complexity of Counting Sort, a non-comparison-based sorting algorithm. We’ll explore how it works, its efficiency, and its suitability for various datasets.
What is Counting Sort?
Counting Sort is an integer sorting algorithm that works by counting the occurrences of each element and using that information to determine the sorted order. It is particularly effective for datasets where the range of values (kk) is not significantly larger than the number of elements (nn).
Steps in Counting Sort
- Counting Occurrences: Create a count array to store the frequency of each unique element.
- Cumulative Count: Transform the count array to store cumulative sums.
- Placement: Use the cumulative count to place elements into their correct positions in the output array.
Time Complexity Analysis
1. Best Case Time Complexity
- In the best case, the algorithm iterates through the input array once to populate the count array and once again to construct the sorted output.
- Best Case Complexity: O(n + k), where:
- nn is the number of elements in the input array.
- kk is the range of input values.
2. Worst Case Time Complexity
- In the worst case, the operations of counting, cumulative summation, and placement are still performed linearly with respect to n + k.
- Worst Case Complexity: O(n + k).
3. Average Case Time Complexity
- On average, Counting Sort maintains its efficiency as it doesn’t depend on the initial order of elements.
- Average Case Complexity: O(n + k).
Space Complexity
Counting Sort requires additional space for the count array and the output array. The space complexity is:
- O(n + k), where nn is for the output array, and kk is for the count array.
Comparison with Other Sorting Algorithms
| Sorting Algorithm | Best Case | Worst Case | Average Case | Space Complexity |
|---|---|---|---|---|
| Counting Sort | O(n + k) | O(n + k) | O(n + k) | O(n + k) |
| Quick Sort | O(n \log n) | O(n^2) | O(n \log n) | O(\log n) |
| Merge Sort | O(n \log n) | O(n \log n) | O(n \log n) | O(n) |
| Bubble Sort | O(n) | O(n^2) | O(n^2) | O(1) |
Advantages of Counting Sort
- Linear Time: Performs in linear time for small kk, making it faster than comparison-based algorithms for certain cases.
- Stable Sort: Maintains the relative order of elements with equal keys.
- Efficient for Integers: Best suited for datasets with a narrow range of integers.
Limitations of Counting Sort
- Large Range Problem: Becomes inefficient if kk (range of input values) is significantly larger than nn (number of elements).
- Additional Space: Requires extra memory for the count and output arrays, which may be prohibitive for large datasets.
- Not Comparison-Based: Limited to integer data or data that can be mapped to a range of integers.
Practical Use Case
Counting Sort is ideal for scenarios like:
- Sorting exam scores where the range is fixed (e.g., 0–100).
- Grouping items with known bounded keys.
Conclusion
Counting Sort offers linear time complexity (O(n+k)O(n + k)) and is an excellent choice for sorting datasets with small, fixed ranges of integers. However, its efficiency diminishes as the range of values increases.