Output array
- Algorithms course
- Intermediate
- Lesson 15/80
- 4 min
Use the count array to produce a stable output.
Output array
The output array is built from the cumulative count. Each element is placed at the position the cumulative count points to; this finds the correct sorted position.
For stability we walk the array back to front: output[count[arr[i]] - 1] = arr[i], then count[arr[i]] -= 1. This preserves the order of equal-key elements.
Going backwards preserves the relative order of equal elements. This makes counting sort stable and the foundation of radix sort.
Stability
By placing back to front, counting sort is stable. The first equal element stays first in the sorted array; this order is preserved without change.
This matters when sorting records with satellite data: records with equal keys keep their original order and secondary information is not lost.
Radix sort's stability relies on this counting sort stability; that is why radix sort uses counting sort for each digit pass.
Practice Counting sort
Write counting_sort(arr). Count array + cumulative + place backward. Print [1, 2, 2, 3, 3, 4, 8] with print(counting_sort([4, 2, 2, 8, 3, 3, 1])).
Starter code
def counting_sort(arr):
# Counting sortSample solution
def counting_sort(arr):
# Counting sort
if not arr:
return []
k = max(arr) + 1
count = [0] * k
for x in arr:
count[x] += 1
for i in range(1, k):
count[i] += count[i - 1]
output = [0] * len(arr)
for i in range(len(arr) - 1, -1, -1):
output[count[arr[i]] - 1] = arr[i]
count[arr[i]] -= 1
return output
print(counting_sort([4, 2, 2, 8, 3, 3, 1]))Expected output
[1, 2, 2, 3, 3, 4, 8]
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Output array: match the terms
| Term | Meaning |
|---|---|
Output |
output |
Cumulative |
Position |
Walk backward |
Stable |
count -= 1 |
Free slot |
2 Why is counting sort stable?
- Random order
- No comparison
- Only on small arrays
- It places back to front Correct answer
Explanation: It places back to front
3 Placement
output[count[arr[i]] - ____] = arr[i]output[count[arr[i]] - 1] = arr[i]Explanation: 1 is right.