Sorting is a fundamental part of programming, and mastering efficient sorting algorithms can significantly improve the performance of your programs. Radix Sort is a unique algorithm that sorts numbers digit by digit, rather than comparing them directly like Quick Sort or Merge Sort. This method allows Radix Sort to efficiently handle large datasets, especially when dealing with integers or fixed-length strings.
with hands-on learning.
get the skills and confidence to land your next move.
Radix Sort is widely used in data processing, digital systems, and other scenarios where numeric sorting is frequent. For beginners, learning Radix Sort is a great way to understand non-comparative sorting techniques. The algorithm works by processing each digit of the numbers, starting either from the least significant digit (LSD) or the most significant digit (MSD). Implementing Radix Sort in Python is an excellent way to practice arrays, loops, and helper functions while gaining insight into efficient sorting strategies.
Program 1: Basic Radix Sort Using Least Significant Digit
This program demonstrates the classic Radix Sort approach using the least significant digit first. It sorts an array of integers by repeatedly grouping numbers based on individual digits.
def counting_sort(arr, exp):
n = len(arr)
output = [0] * n
count = [0] * 10
for i in range(n):
index = arr[i] // 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):
max_num = max(arr)
exp = 1
while max_num // exp > 0:
counting_sort(arr, exp)
exp *= 10
numbers = [170, 45, 75, 90, 802, 24, 2, 66]
print("Original List:", numbers)
radix_sort(numbers)
print("Sorted List:", numbers)In this program, counting_sort is used for each digit, starting from the least significant one. The algorithm maintains stability, ensuring that equal numbers retain their relative order. Beginners can understand how breaking numbers into digits simplifies the sorting process.
Program 2: Radix Sort Using Most Significant Digit
Radix Sort can also process numbers starting from the most significant digit, which often requires a recursive approach. This method is particularly useful for sorting large numbers efficiently.
def radix_sort_msd(arr, exp):
if len(arr) <= 1 or exp == 0:
return
buckets = [[] for _ in range(10)]
for num in arr:
index = (num // exp) % 10
buckets[index].append(num)
idx = 0
for bucket in buckets:
radix_sort_msd(bucket, exp // 10)
for num in bucket:
arr[idx] = num
idx += 1
numbers = [170, 45, 75, 90, 802, 24, 2, 66]
max_num = max(numbers)
exp = 1
while max_num // exp >= 10:
exp *= 10
print("Original List:", numbers)
radix_sort_msd(numbers, exp)
print("Sorted List:", numbers)This MSD approach uses recursion to process numbers starting from the highest place value. Beginners can see how recursion allows the algorithm to break down the problem into smaller, manageable parts while maintaining order.
Program 3: Radix Sort in Descending Order
Radix Sort can be adapted to sort numbers in descending order by modifying the counting process to place higher digits first. This version ensures that the largest numbers come to the front.
def counting_sort_desc(arr, exp):
n = len(arr)
output = [0] * n
count = [0] * 10
for i in range(n):
index = (arr[i] // exp) % 10
count[index] += 1
for i in range(8, -1, -1):
count[i] += count[i + 1]
i = n - 1
while i >= 0:
index = (arr[i] // exp) % 10
output[count[index] - 1] = arr[i]
count[index] -= 1
i -= 1
for i in range(n):
arr[i] = output[i]
def radix_sort_desc(arr):
max_num = max(arr)
exp = 1
while max_num // exp > 0:
counting_sort_desc(arr, exp)
exp *= 10
return arr
numbers = [121, 432, 564, 23, 1, 45, 788]
sorted_numbers = radix_sort_desc(numbers)
print("Sorted list in descending order:", sorted_numbers)In this program, the counting array is accumulated in reverse order, ensuring that larger digits are placed first. Beginners can see how small changes in logic allow the algorithm to sort in the opposite order without changing the core structure of Radix Sort.
Program 4: Radix Sort Handling Negative Numbers
Standard Radix Sort only handles positive integers. This program demonstrates how to extend it to sort arrays containing both negative and positive numbers.
def counting_sort(arr, exp):
n = len(arr)
output = [0] * n
count = [0] * 10
for i in range(n):
index = arr[i] // 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):
max_num = max(arr)
exp = 1
while max_num // exp > 0:
counting_sort(arr, exp)
exp *= 10
def radix_sort_with_negatives(arr):
positives = [x for x in arr if x >= 0]
negatives = [-x for x in arr if x < 0]
radix_sort(positives)
radix_sort(negatives)
negatives = [-x for x in reversed(negatives)]
arr[:] = negatives + positives
numbers = [170, -45, 75, -90, 802, 24, -2, 66]
print("Original List:", numbers)
radix_sort_with_negatives(numbers)
print("Sorted List:", numbers)This program separates positive and negative numbers, sorts them individually using the standard Radix Sort, and then combines them. Beginners can learn how simple transformations allow Radix Sort to handle a wider range of inputs efficiently.
Program 5: Radix Sort Using Buckets
Instead of counting sort, Radix Sort can use dynamic buckets for each digit. This method simplifies the implementation and makes it more visual.
def radix_sort_buckets(arr):
max_num = max(arr)
exp = 1
while max_num // exp > 0:
# Create 10 empty buckets for each digit (0–9)
buckets = [[] for _ in range(10)]
# Place each number in the corresponding bucket
for num in arr:
index = (num // exp) % 10
buckets[index].append(num)
# Flatten the buckets back into the list
arr[:] = [num for bucket in buckets for num in bucket]
# Move to the next digit
exp *= 10
numbers = [170, 45, 75, 90, 802, 24, 2, 66]
print("Original List:", numbers)
radix_sort_buckets(numbers)
print("Sorted List:", numbers)Using buckets demonstrates a more intuitive way to group numbers by digits. Beginners can understand how grouping and concatenating numbers helps achieve sorting step by step.
Program 6: Radix Sort for String Numbers
Radix Sort can also sort string representations of numbers efficiently, which is useful in data processing scenarios.
def radix_sort_strings(arr):
if not arr:
return
max_len = max(len(s) for s in arr)
# Process from least-significant digit (rightmost) to leftmost
for pos in range(1, max_len + 1):
buckets = [[] for _ in range(10)]
for num in arr:
digit = int(num[-pos]) if len(num) >= pos else 0
buckets[digit].append(num)
arr[:] = [n for bucket in buckets for n in bucket]
numbers = ['170', '45', '75', '90', '802', '24', '2', '66']
print("Original List:", numbers)
radix_sort_strings(numbers)
print("Sorted List:", numbers)Sorting string numbers demonstrates the flexibility of Radix Sort. Beginners can see how the algorithm adapts to textual representations while maintaining digit-based ordering.
Program 7: Radix Sort Using Python Lists Only
Radix Sort can also be implemented without a separate counting sort function by using Python lists to group numbers by their digits directly. This version helps beginners understand the grouping concept in a more intuitive way.
def radix_sort_lists(arr):
max_num = max(arr)
exp = 1
while max_num // exp > 0:
buckets = [[] for _ in range(10)]
for num in arr:
index = (num // exp) % 10
buckets[index].append(num)
arr = [num for bucket in buckets for num in bucket]
exp *= 10
return arr
numbers = [329, 457, 657, 839, 436, 720, 355]
sorted_numbers = radix_sort_lists(numbers)
print("Sorted list using lists:", sorted_numbers)In this version, each digit determines which bucket a number goes into. After processing all numbers, the buckets are combined in order. This method makes it easy for beginners to visualize how numbers are grouped and sorted by digits, reinforcing the core principle of Radix Sort without relying on counting arrays.
Frequently Asked Questions (FAQ)
Radix Sort can raise some common questions for beginners. Here are answers to make it easier to understand.
Q1: What is the time complexity of Radix Sort?
Radix Sort has O(nk) complexity, where n is the number of elements and k is the number of digits in the largest number.
Q2: Is Radix Sort stable?
Yes, Radix Sort is stable, meaning equal elements retain their original order.
Q3: Can Radix Sort handle negative numbers?
Yes, by separating positives and negatives, sorting them, and then recombining.
Q4: When should Radix Sort be used?
It is ideal for large datasets of integers or fixed-length strings where comparisons are costly.
Q5: Can Radix Sort sort strings?
Yes, it can sort strings representing numbers or fixed-length sequences efficiently.
Conclusion
Radix Sort is a powerful, versatile sorting algorithm that goes beyond traditional comparison-based methods. In this article, we explored multiple implementations, including LSD and MSD approaches, handling negative numbers, using buckets, and sorting string representations of numbers.
For beginners, practicing Radix Sort helps improve understanding of arrays, loops, recursion, and data manipulation. Experimenting with different data types and approaches builds a strong foundation in algorithmic thinking and efficient problem-solving in Python.
