Counting idea
- Algorithms course
- Intermediate
- Lesson 13/80
- 4 min
Count each value, use cumulative sums to sort.
Counting idea
Counting sort sorts without comparisons. It counts how many times each element appears, then builds the sorted output from these counts.
When keys are in a small integer range it runs in O(n + k); k is the key range. Faster than comparison sorts.
But if the range is large, k memory explodes. So it suits only small-range integer keys.
Range cost
Counting sort builds a count array from 0 to max(arr). The range is k = max - min + 1.
Memory is O(k). If k is very large (e.g. 0 to a million), storing this array is costly.
So counting sort is best on dense, narrow ranges. For negative numbers an offset is needed.
Practice Count elements
Write count_value(arr, v). Count how many times v appears in arr. Print 3 with print(count_value([3, 1, 4, 1, 5, 1], 1)).
Starter code
def count_value(arr, v):
# Count vSample solution
def count_value(arr, v):
# Count v
count = 0
for x in arr:
if x == v:
count += 1
return count
print(count_value([3, 1, 4, 1, 5, 1], 1))Expected output
3
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 When is counting sort efficient?
- Always
- On a small integer range Correct answer
- Only on large arrays
- Only on text
Explanation: On a small integer range
2 Range size
k = max(arr) - min(arr) + ____k = max(arr) - min(arr) + 1Explanation: 1 is right.
3 Counting idea: match the terms
| Term | Meaning |
|---|---|
Counting sort |
No comparison |
Cost |
O(n+k) |
Memory |
O(k) |
Range |
Must be narrow |