Radix Sort Algorithm

Introduction to Radix Sort

Radix sort is a non-comparative sorting algorithm that sorts integers by processing individual digits. It works by sorting the numbers by their least significant digit and then by each subsequent significant digit. This process continues until all digits are sorted. Radix sort can be more efficient than comparison-based sorting algorithms, especially for large lists of integers.

---

Step-by-Step Process

Consider an array with the following elements:

[170, 45, 75, 90, 802, 24, 2, 66]

To sort this array using radix sort, follow these steps:

1. Find the Maximum Number: Determine the maximum number in the array to know the number of digits.
2. Sort by Each Digit: Start from the least significant digit (units place) and sort the array based on that digit. Then move to the next significant digit (tens place) and sort the array. Repeat this process for all digits.

Let's apply these steps to the example array:

• Initial array: [170, 45, 75, 90, 802, 24, 2, 66]
• Sort by units place: [170, 90, 802, 2, 24, 45, 75, 66]
• Sort by tens place: [802, 2, 24, 45, 66, 170, 75, 90]
• Sort by hundreds place: [2, 24, 45, 66, 75, 90, 170, 802]
• Final sorted array: [2, 24, 45, 66, 75, 90, 170, 802]

---

Pseudo Code for Radix Sort

Below is the pseudo code for the radix sort algorithm:

function radixSort(array)
    maxNumber = getMax(array)
    exp = 1
    while maxNumber / exp > 0 do
        countSort(array, exp)
        exp = exp * 10
    end while
end function

function countSort(array, exp)
    n = length(array)
    output = array of size n
    count = array of size 10 with zeros

    for i = 0 to n - 1 do
        index = (array[i] / exp) % 10
        count[index] += 1
    end for

    for i = 1 to 9 do
        count[i] += count[i - 1]
    end for

    for i = n - 1 down to 0 do
        index = (array[i] / exp) % 10
        output[count[index] - 1] = array[i]
        count[index] -= 1
    end for

    for i = 0 to n - 1 do
        array[i] = output[i]
    end for
end function

Explanation:

• Initialize: The radixSort function starts by finding the maximum number in the array to determine the number of digits. It then initializes the exponent (exp) to 1.
• Count Sort for Each Digit: The countSort function is called for each digit, starting from the least significant digit. The array is sorted based on the current digit using counting sort.
• Update Exponent: After sorting by each digit, the exponent is multiplied by 10 to move to the next significant digit.
• Count Sort Process: The countSort function sorts the array based on the current digit using counting sort. It creates a count array to store the count of each digit, an output array to store the sorted elements, and then updates the original array with the sorted elements.

---

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_num = max(arr)
    exp = 1
    while max_num // exp > 0:
        counting_sort(arr, exp)
        exp *= 10

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

This Python program defines functions to perform radix sort on an array. The counting_sort function sorts the array based on the current digit, and the radix_sort function processes each digit starting from the least significant digit.