What is the Counting Sort ?
Counting Sort is a non-comparison-based sorting algorithm suitable for sorting integers or objects according to keys that are small integers. It counts the number of objects that have distinct key values and uses arithmetic to determine the positions of each key in the output sequence.
Key Characteristics
- Time Complexity: O(n + k), where n is the number of elements and k is the range of the input.
- Space Complexity: O(n + k), as it uses additional arrays for counting and output.
- Stability: Stable (maintains the relative order of equal elements).
- Algorithm Type: Non-comparison-based sorting.
How Counting Sort Works
- Find the Range: Determine the range (k) of the input data.
- Create Count Array: Create a count array to store the count of each unique element.
- Cumulative Count: Modify the count array to store the cumulative count of elements.
- Build Output Array: Build the output array by placing elements in their correct positions based on the cumulative count.
Steps and Example
Consider the following unsorted array:
[4, 2, 2, 8, 3, 3, 1]Step 1: Find the Range
- The range kkk of the input data is from 1 to 8.
Step 2: Create Count Array
- Initialize the count array with zeros:
count = [0, 0, 0, 0, 0, 0, 0, 0, 0] - Count each element:
count = [0, 1, 2, 2, 1, 0, 0, 0, 1]
Step 3: Cumulative Count
- Modify the count array to store the cumulative count of elements:
count = [0, 1, 3, 5, 6, 6, 6, 6, 7]
Step 4: Build Output Array
- Initialize the output array:
output = [0, 0, 0, 0, 0, 0, 0] - Place elements in their correct positions:
output = [1, 2, 2, 3, 3, 4, 8]
Visualization
Let’s generate a step-by-step visualization of Counting Sort using diagrams.
Initial Array
[4, 2, 2, 8, 3, 3, 1]Step 2: Count Array
Original array: [4, 2, 2, 8, 3, 3, 1]
Count array after counting elements:
[0, 1, 2, 2, 1, 0, 0, 0, 1]Step 3: Cumulative Count Array
Count array after cumulative count:
[0, 1, 3, 5, 6, 6, 6, 6, 7]Step 4: Output Array
Placing elements into the output array:
Original array: [4, 2, 2, 8, 3, 3, 1]
Output array: [1, 2, 2, 3, 3, 4, 8]