Radix Sort
Radix sort is a non-comparative sorting algorithm that sorts data with integer keys by grouping keys by the individual digits which share the same significant position and value. It uses counting sort as a subroutine to sort the array according to each digit.
Algorithm Overview
Radix sort works by processing digits of numbers from least significant to most significant (or vice versa). For each digit position, it uses a stable sorting algorithm (counting sort) to sort the entire array based on that digit. The stability ensures that numbers with the same digit maintain their relative order from previous sorting passes.
Key Features
- Non-Comparative: Sorts by examining digits, not comparing elements
- Stable: Maintains relative order of equal elements
- Digit-Based: Processes one digit position at a time
- Linear Time: O(d × (n + k)) where d is number of digits
- Multiple Implementations: Basic, verbose, string-based, and different base versions
Time and Space Complexity
- Time Complexity: O(d × (n + k)) where:
- d = number of digits in largest number
- n = number of elements
- k = range of each digit (10 for decimal)
- Space Complexity: O(n + k) for the counting sort subroutine
- When d is constant: Effectively O(n) - linear time!
Algorithm Steps
- Find the maximum number to determine number of digits
- For each digit position (from least to most significant):
- Extract the digit at current position for each number
- Apply counting sort based on this digit
- Maintain stability to preserve order from previous passes
- Result: Array is sorted after processing all digit positions
Usage Examples
Basic Usage
from algo.algorithms.sorting.radix_sort import radix_sort
# Sort integers
numbers = [170, 45, 75, 90, 2, 802, 24, 66]
sorted_numbers = radix_sort(numbers)
print(sorted_numbers) # [2, 24, 45, 66, 75, 90, 170, 802]
# Another example
result = radix_sort([329, 457, 657, 839, 436, 720, 355])
print(result) # [329, 355, 436, 457, 657, 720, 839]
# Empty array
result = radix_sort([])
print(result) # []
Educational/Debugging
from algo.algorithms.sorting.radix_sort import radix_sort_verbose
# See step-by-step process
radix_sort_verbose([170, 45, 75, 90, 2])
Output:
Starting radix sort on: [170, 45, 75, 90, 2]
Maximum number: 170 (has 3 digits)
Sorting by digit at position 1 (exp = 1):
Digits being sorted: 170→0 45→5 75→5 90→0 2→2
After sorting by digit 1: [170, 90, 2, 45, 75]
Sorting by digit at position 2 (exp = 10):
Digits being sorted: 170→7 90→9 2→0 45→4 75→7
After sorting by digit 2: [2, 45, 170, 75, 90]
Sorting by digit at position 3 (exp = 100):
Digits being sorted: 2→0 45→0 170→1 75→0 90→0
After sorting by digit 3: [2, 45, 75, 90, 170]
Final sorted array: [2, 45, 75, 90, 170]
Different Bases
from algo.algorithms.sorting.radix_sort import radix_sort_base
# Sort using different base (e.g., binary)
numbers = [7, 3, 15, 1, 8]
binary_sorted = radix_sort_base(numbers, base=2)
print(binary_sorted) # [1, 3, 7, 8, 15]
# Sort using base 16 (hexadecimal)
hex_sorted = radix_sort_base(numbers, base=16)
print(hex_sorted) # [1, 3, 7, 8, 15]
String-Based Implementation
from algo.algorithms.sorting.radix_sort import radix_sort_with_strings
# Alternative implementation using string representation
numbers = [170, 45, 75, 90, 2]
result = radix_sort_with_strings(numbers)
print(result) # [2, 45, 75, 90, 170]
Edge Cases Handled
# Empty array
result = radix_sort([]) # Returns []
# Single element
result = radix_sort([42]) # Returns [42]
# All same elements
result = radix_sort([555, 555, 555]) # Returns [555, 555, 555]
# Large numbers
large_nums = [999999, 1, 888888]
result = radix_sort(large_nums) # Returns [1, 888888, 999999]
# Negative numbers (raises error)
try:
radix_sort([-1, 2, 3])
except ValueError as e:
print(e) # "Radix sort only works with non-negative integers"
API Reference
Radix Sort Algorithm Implementation
Radix sort is a non-comparative sorting algorithm that sorts data with integer keys by grouping keys by the individual digits which share the same significant position and value. It uses counting sort as a subroutine to sort the array according to each digit.
Time Complexity: O(d * (n + k)) where d is the number of digits, n is the number of elements, k is the range of digits (0-9)
Space Complexity: O(n + k) for the counting sort subroutine
Stability: Stable (maintains relative order of equal elements)
Note: Only works with non-negative integers in this implementation
count_digits(num)
Count the number of digits in a number.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
num
|
int
|
The number to count digits for |
required |
Returns:
| Type | Description |
|---|---|
int
|
The number of digits in the number |
counting_sort_for_radix(arr, exp)
Counting sort implementation used as a subroutine for radix sort. Sorts the array according to the digit at the given exponent position.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
arr
|
List[int]
|
List of non-negative integers to sort |
required |
exp
|
int
|
The exponent (1 for units, 10 for tens, 100 for hundreds, etc.) |
required |
Returns:
| Type | Description |
|---|---|
List[int]
|
The sorted array according to the digit at exp position |
get_max_value(arr)
Find the maximum value in the array.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
arr
|
List[int]
|
List of integers |
required |
Returns:
| Type | Description |
|---|---|
int
|
The maximum value in the array |
radix_sort(arr)
Sort an array of non-negative integers using the radix sort algorithm.
The algorithm works by sorting the elements digit by digit, starting from the least significant digit (units) to the most significant digit. It uses counting sort as a stable sorting subroutine for each digit.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
arr
|
List[int]
|
List of non-negative integers to sort |
required |
Returns:
| Type | Description |
|---|---|
List[int]
|
The sorted list (sorted in-place, but also returned for convenience) |
Raises:
| Type | Description |
|---|---|
ValueError
|
If the array contains negative numbers |
Examples:
radix_sort_base(arr, base=10)
Generalized radix sort that works with different bases.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
arr
|
List[int]
|
List of non-negative integers to sort |
required |
base
|
int
|
The base to use for sorting (default is 10 for decimal) |
10
|
Returns:
| Type | Description |
|---|---|
List[int]
|
The sorted list |
Raises:
| Type | Description |
|---|---|
ValueError
|
If the array contains negative numbers or base is invalid |
radix_sort_verbose(arr)
Radix sort with detailed step-by-step output for educational purposes.
This version prints each step of the sorting process to help understand how the algorithm works.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
arr
|
List[int]
|
List of non-negative integers to sort |
required |
Returns:
| Type | Description |
|---|---|
List[int]
|
The sorted list |
Raises:
| Type | Description |
|---|---|
ValueError
|
If the array contains negative numbers |
radix_sort_with_strings(arr)
Alternative implementation that works with string representation of numbers. This can be easier to understand but is less efficient.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
arr
|
List[int]
|
List of non-negative integers to sort |
required |
Returns:
| Type | Description |
|---|---|
List[int]
|
The sorted list |
Raises:
| Type | Description |
|---|---|
ValueError
|
If the array contains negative numbers |