Python Radix Sort

Python Radix Sort

Radix Sort is another non-comparison-based integer sorting algorithm. It sorts integers by processing individual digits. Because integers can have different numbers of digits, the algorithm groups keys by the same digit at the same significant position.

For example, it first sorts the numbers based on the least significant digit (the "1s" place), then the next digit (the "10s" place), and so on, up to the most significant digit.

Radix sort uses Counting Sort as a subroutine to sort the digits at each position.

How Radix Sort Works

1. Find the maximum number in the list to determine the number of digits in the largest number.
2. Start a loop that goes from the least significant digit to the most significant digit (e.g., 1s place, 10s place, 100s place, etc.).
3. In each iteration of the loop, use a stable sorting algorithm (like Counting Sort) to sort the numbers based on the current digit.
4. After the loop finishes (i.e., after sorting by the most significant digit), the list will be fully sorted.

Implementing Radix Sort in Python

The implementation requires a helper function for counting sort that is modified to sort based on a specific digit.

// A function to do counting sort of arr[] according to
// the digit represented by exp.
def counting_sort_for_radix(data, exp):
    n = len(data)
    output = [0] * n
    count = [0] * 10 // Digits 0-9
    // Store count of occurrences in count[]
    for i in range(n):
        index = data[i] // exp
        count[index % 10] += 1
    // Change count[i] so that count[i] now contains actual
    // position of this digit in output[]
    for i in range(1, 10):
        count[i] += count[i - 1]
    // Build the output array
    i = n - 1
    while i >= 0:
        index = data[i] // exp
        output[count[index % 10] - 1] = data[i]
        count[index % 10] -= 1
        i -= 1
    // Copying the output array to data[]
    for i in range(len(data)):
        data[i] = output[i]

// The main function to implement Radix Sort
def radix_sort(data):
    // Find the maximum number to know number of digits
    max_val = max(data)
    // Do counting sort for every digit. Note that instead
    // of passing digit number, exp is passed. exp is 10^i
    // where i is current digit number
    exp = 1
    while max_val / exp > 0:
        counting_sort_for_radix(data, exp)
        exp *= 10
// --- Usage ---
my_list = [170, 45, 75, 90, 802, 24, 2, 66]
radix_sort(my_list)
print("Sorted list is:", my_list)

Time and Space Complexity

Let d be the number of digits in the maximum number and n be the number of elements.

• Time Complexity: O(d * (n + k)), where k is the base of the number system (10 for decimal). Since d and k are often constants, the complexity is effectively linear, O(n).
• Space Complexity: O(n + k) from the underlying counting sort.