Stable sub-sort
- Algorithms course
- Intermediate
- Lesson 19/80
- 4 min
A stable sub-sort keeps previous passes intact.
Stable sub-sort
Full radix sort repeats the digit pass for every digit. It starts from the least significant and goes to the most significant.
Because each pass is stable, the order from the previous pass is preserved and the new digit adds information. At the end the array is fully sorted.
The digit count is d = len(str(max(arr))). Total cost O(dn).
Negative numbers
Radix sort by default sorts non-negative integers. For negative numbers there are two common methods.
First: add a fixed offset to all numbers to make them positive, sort, then subtract the offset. Second: split by sign and absolute value.
Both keep the O(dn) cost, but the implementation needs more care.
Practice Radix sort
Write radix_sort(arr). Sort digit by digit with LSD. Print [2, 24, 45, 75, 90, 170] with print(radix_sort([170, 45, 75, 90, 2, 24])).
Starter code
def radix_sort(arr):
# Sort digit by digitSample solution
def get_digit(n, d):
return n // (10 ** d) % 10
def counting_by_digit(arr, d):
count = [0] * 10
for x in arr:
count[get_digit(x, d)] += 1
for i in range(1, 10):
count[i] += count[i - 1]
output = [0] * len(arr)
for i in range(len(arr) - 1, -1, -1):
digit = get_digit(arr[i], d)
output[count[digit] - 1] = arr[i]
count[digit] -= 1
return output
def radix_sort(arr):
# Sort digit by digit
if not arr:
return arr
max_digits = len(str(max(arr)))
for d in range(max_digits):
arr = counting_by_digit(arr, d)
return arr
print(radix_sort([170, 45, 75, 90, 2, 24]))Expected output
[2, 24, 45, 75, 90, 170]
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Stable sub-sort: match the terms
| Term | Meaning |
|---|---|
LSD |
Start |
Pass |
Stable |
Digit count |
d |
Total |
O(dn) |
2 How many passes does radix sort do?
- 1
- log n
- n
- d (digit count) Correct answer
Explanation: d (digit count)
3 Loop bound
for d in range(____):for d in range(max_digits):Explanation: max_digits is right.