Counting Sort
Problem
Counting Sort is a non-comparison-based sorting algorithm that works well when there is a limited range of input values. It counts the number of occurrences of each element and uses this information to place elements in their correct sorted positions.
Examples:
Example 1:
Input: arr = [4, 2, 2, 8, 3, 3, 1]
Output: [1, 2, 2, 3, 3, 4, 8]
Explanation: The algorithm counts the occurrences of each element and places them in their correct sorted positions.
Example 2:
Input: arr = [5, 2, 9, 5, 2, 3, 5]
Output: [2, 2, 3, 5, 5, 5, 9]
Explanation: The algorithm efficiently sorts the array by counting the occurrences of each element.
Solution
Intuition
- Counting Sort is efficient when the range of input values is not significantly larger than the number of elements to be sorted.
- It works by counting the occurrences of each distinct element in the input array.
- Then, it calculates the position of each element in the output array based on these counts.
- Unlike comparison-based sorting algorithms, Counting Sort has a linear time complexity when the range of input values is fixed.
Approach
- Find the range of input values (minimum to maximum).
- Create a count array to store the count of each unique element.
- Modify the count array such that each element at each index stores the sum of previous counts (cumulative count).
- Build the output array by placing each element at its correct position based on the count array.
- Copy the output array back to the original array (if needed).
Complexity Analysis
- Time Complexity: O(n + k) where n is the number of elements and k is the range of input values.
- Space Complexity: O(n + k) for the output array and the count array.
Implementation
CPP
Run your code to see output here