Python Radix Sort Tutorial: Sorting Integers, Negatives, and Floats
A Complete Guide to Radix Sort in Python with Examples
Python Sorting Algorithms: Radix Sort Explained
Efficient Number Sorting in Python Using Radix Sort
Radix Sort in Python: From Positive Integers to Floats
Introduction to Radix Sort in Python
Radix Sort is a non-comparative sorting algorithm that works by sorting numbers digit by digit. Instead of comparing entire numbers directly, it distributes elements into “buckets” based on their digits or characters, and processes one digit position at a time.
For integers, Radix Sort typically works from the least significant digit (LSD) to the most significant digit (MSD). This ensures stability and produces a sorted array after processing all digit positions.
—
How Radix Sort Works
- Find the maximum number to determine how many digits we need to process.
- Perform a stable sort (like Counting Sort) for each digit position (units, tens, hundreds, etc.).
- Repeat until all digit positions are processed.
Example: sorting the array [170, 45, 75, 90, 802, 24, 2, 66]:
- Sort by units digit → [170, 90, 802, 2, 24, 45, 75, 66]
- Sort by tens digit → [802, 2, 24, 45, 66, 170, 75, 90]
- Sort by hundreds digit → [2, 24, 45, 66, 75, 90, 170, 802]
The array is now sorted.
—
Python Implementation for Positive Integers
def counting_sort(arr, exp):
n = len(arr)
output = [0] * n
count = [0] * 10
for num in arr:
index = (num // exp) % 10
count[index] += 1
for i in range(1, 10):
count[i] += count[i - 1]
for i in range(n - 1, -1, -1):
index = (arr[i] // exp) % 10
output[count[index] - 1] = arr[i]
count[index] -= 1
for i in range(n):
arr[i] = output[i]
def radix_sort(arr):
if not arr:
return arr
max_num = max(arr)
exp = 1
while max_num // exp > 0:
counting_sort(arr, exp)
exp *= 10
# Example
arr = [170, 45, 75, 90, 802, 24, 2, 66]
radix_sort(arr)
print("Sorted array:", arr)
—
Extending to Negative Integers
- Separate negatives and non-negatives.
- Convert negatives to positives with absolute value.
- Apply Radix Sort separately.
- Reverse the negatives (since larger absolute value means smaller actual value).
- Merge negatives + non-negatives.
def radix_sort_positive(arr):
if not arr:
return arr
max_num = max(arr)
exp = 1
while max_num // exp > 0:
counting_sort(arr, exp)
exp *= 10
def radix_sort(arr):
negatives = [-x for x in arr if x < 0]
non_negatives = [x for x in arr if x >= 0]
radix_sort_positive(negatives)
radix_sort_positive(non_negatives)
negatives = [-x for x in reversed(negatives)]
return negatives + non_negatives
# Example
arr = [170, -45, 75, -90, 802, 24, -2, 66]
sorted_arr = radix_sort(arr)
print("Sorted array:", sorted_arr)
—
Sorting Floating-Point Numbers
Floats can also be sorted with Radix Sort by transforming them into integers. Common methods:
- Scaling: multiply all floats by a power of 10 to convert them to integers (works for fixed precision floats).
- Bit reinterpretation: treat IEEE 754 float bits as integers, adjusting negatives to maintain order.
Here is a Python example using scaling for positive floats:
def radix_sort_floats(arr, precision=2):
# Scale floats to integers
factor = 10 ** precision
int_arr = [int(x * factor) for x in arr]
radix_sort(int_arr)
# Convert back to floats
return [x / factor for x in int_arr]
# Example
arr = [3.14, 2.71, 1.41, 0.99, 2.0]
sorted_arr = radix_sort_floats(arr)
print("Sorted floats:", sorted_arr)
—
Output
Sorted floats: [0.99, 1.41, 2.0, 2.71, 3.14]
—
When to Use Radix Sort
- Sorting large numbers of integers with relatively small maximum values.
- Sorting fixed-length strings efficiently.
- Linear-time sorting is required in practice for fixed-width integers or scaled floats.
—
Limitations
- Not a general-purpose sorting algorithm; best for integers or fixed-length keys.
- Requires additional space for buckets (not in-place).
- For arbitrary floats or mixed types, comparison-based sorts like Timsort are safer.
—
Conclusion
Radix Sort is a fast, digit-based sorting algorithm that can handle integers, negatives, and fixed-precision floats. While not as flexible as comparison-based sorts, it offers linear-time performance in the right scenarios. By transforming floats properly, you can extend Radix Sort beyond integers.
–EOF (The Ultimate Computing & Technology Blog) —
Last Post: A Complete Guide to Sorted Data Structures in Python
Next Post: Chessly (British Short Hairs) Classified as Persian Cat by ResNet-50