Radix Sort Algorithm

Radix Sort is a non-comparison-based sorting algorithm that sorts numbers by processing individual digits. It works by sorting the numbers based on their digit values, starting from the least significant digit (LSD) to the most significant digit (MSD). Radix Sort is efficient for sorting large lists of numbers, especially when the numbers have a fixed number of digits.

Radix Sort can be implemented using a stable intermediate sorting algorithm, such as Counting Sort, to sort the numbers based on individual digit values.

Radix Sort Algorithm Implementation in Python

def counting_sort(arr, exp):
    n = len(arr)
    output = [0] * n  # Output array
    count = [0] * 10  # Count array for digits (0 to 9)

    # Store the count of occurrences of each digit
    for i in range(n):
        index = arr[i] // exp
        count[index % 10] += 1

    # Change count[i] so that it contains the 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 = arr[i] // exp
        output[count[index % 10] - 1] = arr[i]
        count[index % 10] -= 1
        i -= 1

    # Copy the output array to arr[], so that arr[] now contains sorted numbers
    for i in range(len(arr)):
        arr[i] = output[i]

def radix_sort(arr):
    # Find the maximum number to determine the number of digits
    max_num = max(arr)

    # Apply counting sort to sort elements based on each digit
    exp = 1
    while max_num // exp > 0:
        counting_sort(arr, exp)
        exp *= 10

    return arr

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

Code Explanation

Counting Sort Function for Radix Sort

def counting_sort(arr, exp):
    n = len(arr)
    output = [0] * n  # Output array
    count = [0] * 10  # Count array for digits (0 to 9)

• The counting_sort function takes an array arr and an exponent exp as parameters. exp determines the digit to be sorted.
• n is the length of the array.
• output is initialized to store the sorted array.
• count is initialized to store the count of digit occurrences (0 to 9).

Store the Count of Occurrences

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

• The loop iterates through the array and calculates the digit at the current exponent position (index % 10).
• The count of each digit is stored in the count array.

Calculate Cumulative Count

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

• The cumulative count of digits is calculated to determine the position of each digit in the output array.

Build the Output Array

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

• The loop iterates through the array in reverse order to maintain the stability of the sort.
• Each element is placed in its correct position in the output array based on the cumulative count.

Copy the Output Array to the Original Array

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

• The sorted elements from the output array are copied back to the original array arr.

Radix Sort Function

def radix_sort(arr):
    max_num = max(arr)

    exp = 1
    while max_num // exp > 0:
        counting_sort(arr, exp)
        exp *= 10

    return arr

• The radix_sort function finds the maximum number in the array to determine the number of digits.
• The while loop iterates through each digit position (units, tens, hundreds, etc.) by applying counting_sort on the array.
• The exp variable is multiplied by 10 in each iteration to move to the next significant digit.

Example Usage

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

• An example list arr is sorted using the radix_sort function, and the sorted list is printed.

Output

Sorted array is: [2, 24, 45, 66, 75, 90, 170, 802]

• The final output is the sorted array in ascending order.

Summary

Radix Sort is a non-comparison-based sorting algorithm that sorts numbers by processing individual digits, starting from the least significant digit to the most significant digit. It uses a stable intermediate sorting algorithm, such as Counting Sort, to sort the numbers based on individual digit values. Radix Sort is efficient for sorting large lists of numbers with a fixed number of digits, with a time complexity of O(d * (n + k)), where d is the number of digits, n is the number of elements, and k is the range of the digit values.