Python Program to Implement Radix Sort

Radix Sort is a sorting algorithm that operates based on the individual digits of the numbers being sorted. Unlike comparison-based sorting algorithms like Quick Sort or Merge Sort, Radix Sort is a non-comparative sorting algorithm that exploits the structure of the data (integers or strings) to achieve its sorting mechanism.

Problem Statement

You are given an array of non-negative integers. Implement Radix Sort in Python to sort the array in ascending order.

Python Program to Implement Radix Sort

def counting_sort(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10

    for i in range(n):
        index = arr[i] // exp
        count[index % 10] += 1

    for i in range(1, 10):
        count[i] += count[i - 1]

    i = n - 1
    while i >= 0:
        index = arr[i] // exp
        output[count[index % 10] - 1] = arr[i]
        count[index % 10] -= 1
        i -= 1

    for i in range(n):
        arr[i] = output[i]


def radix_sort(arr):
    max_value = max(arr)
    exp = 1
    while max_value // exp > 0:
        counting_sort(arr, exp)
        exp *= 10


# Example usage
arr = [170, 45, 75, 90, 802, 24, 2, 66]
radix_sort(arr)
print("Sorted array:", arr)

How it Works

Step 1: Identify the Maximum Number

• The first step is to identify the maximum number in the list. This is necessary to determine the number of digits in the largest number and the number of iterations required. For example, if the maximum number is 532, then there are three digits, so three iterations will be needed.

Step 2: Sorting by Individual Digits

• Starting from the least significant digit (rightmost digit), Radix Sort performs multiple iterations. In each iteration, it sorts the numbers based on the current digit position using a stable sorting algorithm like Counting Sort.Let’s take an example list [170, 45, 75, 90, 802, 24, 2, 66]:
  • Iteration 1 (Least Significant Digit – LSD):
    • Sort the numbers based on their ones digit (0s place): [170, 90, 801, 2, 72, 45, 75, 66]
  • Iteration 2 (Next Significant Digit):
    • Sort the numbers based on their tens digit (10s place): [801, 2, 72, 802, 24, 45, 75, 66]
  • Iteration 3 (Most Significant Digit – MSD):
    • Sort the numbers based on their hundreds digit (100s place): [2, 24, 45, 66, 72, 75, 801, 802]

Step 3: Repeat for All Digit Positions

• Radix Sort continues these iterations until all digits are sorted. In the case of the example list, since the maximum number has three digits, three iterations are performed.

Step 4: Sorted Result

• After completing all iterations, the list is now sorted. The numbers are ordered from smallest to largest, considering their individual digits.

Key Concepts and Benefits:

• Radix Sort is a non-comparative sorting algorithm, meaning it doesn’t rely on direct comparisons between elements like other sorting algorithms (e.g., QuickSort, MergeSort).
• It leverages the structure of the data itself by sorting based on individual digits, making it efficient for specific scenarios.
• Radix Sort preserves the relative order of elements with equal digits since it employs a stable sorting algorithm for each digit position.
• The time complexity of Radix Sort is O(d * (n + k)), where n is the number of elements, k is the range of values, and d is the number of digits in the maximum number. It can perform well when the number of digits is relatively small.
• Radix Sort can be adapted for sorting strings or other data types as long as there’s a defined ordering.

While Radix Sort might not be the most efficient sorting algorithm for all situations, it serves as a valuable tool when the range of values is not excessively large and the number of digits in the data is reasonable.

Input/ Output