Summary - Radix sort

Implement radix sort and print the result.

Summary - Radix sort

Radix sort: digit by digit, LSD first, with stable counting sort. Non-comparison, O(dn).

d is the digit count; for integers it is log k (k the largest value). Effective even for large numbers.

Negative numbers need an offset. Stability is required; otherwise the result is wrong.

Exercise Summary: radix sort

Write radix_sort(arr). Print [1, 1, 2, 3, 4, 5, 6, 9] with print(radix_sort([3,1,4,1,5,9,2,6])).

Show example 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([3, 1, 4, 1, 5, 9, 2, 6]))

Test yourself

Summary - Radix sort: match the terms

Method

LSD
Sub-sorter

Counting sort
Cost

O(dn)
Stable

Required

Start

Least significant digit: d = ____

Show answer

Least significant digit: d = 0

Does radix sort compare elements?
- No
- Only on small arrays
- Only on large arrays
- Yes
Show answer

No — No

Next lesson: Project: Overview

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies