Radix Sort

Introduction to Radix Sort

Radix sort is a non-comparative integer sorting algorithm. It sorts integers by processing individual digits. Starting from the least significant digit (LSD) to the most significant digit (MSD), it uses a stable subroutine sort (like counting sort) to handle the individual digits. The algorithm is efficient for sorting numbers with a fixed number of digits and works well when the range of digits is not excessively large.

Steps of Radix Sort (Pseudocode Steps)

1. Find the maximum number to determine the number of digits.
2. Initialize: Set up a loop to process each digit from the least significant to the most significant.
3. Digit by digit sorting:
   • Use a stable sort (e.g., counting sort) to sort based on the current digit.
4. Repeat until all digits are processed.

Example

To perform radix sort on the array [170, 45, 75, 90, 802, 24, 2, 66], we follow these steps:

Step 1: Find the largest element in the array, which is 802. It has three digits, so we will iterate three times, once for each significant place.

Step 2: Sort the elements based on the unit place digits (X=0). We use a stable sorting technique, such as counting sort, to sort the digits at each significant place.

Sorting based on the unit place:

Perform counting sort on the array based on the unit place digits. The sorted array based on the unit place is [170, 90, 802, 2, 24, 45, 75, 66].

Step 3: Sort the elements based on the tens place digits.

Sorting based on the tens place:

Perform counting sort on the array based on the tens place digits. The sorted array based on the tens place is [802, 2, 24, 45, 66, 170, 75, 90].

Step 4: Sort the elements based on the hundreds place digits.

Sorting based on the hundreds place:

Perform counting sort on the array based on the hundreds place digits. The sorted array based on the hundreds place is [2, 24, 45, 66, 75, 90, 170, 802].

Step 5: The array is now sorted in ascending order.

The final sorted array using radix sort is [2, 24, 45, 66, 75, 90, 170, 802].

Pseudocode for Radix Sort

function radixSort(array):
    maxNumber = findMax(array)
    numberOfDigits = countDigits(maxNumber)

    for digit in 1 to numberOfDigits:
        countingSortByDigit(array, digit)

function findMax(array):
    maxNumber = array[0]
    for number in array:
        if number > maxNumber:
            maxNumber = number
    return maxNumber

function countDigits(number):
    count = 0
    while number != 0:
        number = number // 10
        count += 1
    return count

function countingSortByDigit(array, digit):
    count = array of size 10 initialized to 0
    output = array of same size as input array

    # Count occurrences of each digit
    for number in array:
        digitValue = (number // 10^(digit - 1)) % 10
        count[digitValue] += 1

    # Change count[i] so that count[i] contains the position of this digit in output
    for i from 1 to 9:
        count[i] += count[i - 1]

    # Build the output array
    for i from length(array) - 1 to 0:
        digitValue = (array[i] // 10^(digit - 1)) % 10
        output[count[digitValue] - 1] = array[i]
        count[digitValue] -= 1

    # Copy the output array to the input array
    for i from 0 to length(array) - 1:
        array[i] = output[i]

Radix Sort Implementation in Python, C++, and Java

Python

def radix_sort(array):
    def counting_sort_by_digit(array, digit):
        count = [0] * 10
        output = [0] * len(array)

        for number in array:
            digit_value = (number // 10**(digit - 1)) % 10
            count[digit_value] += 1

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

        for i in range(len(array) - 1, -1, -1):
            digit_value = (array[i] // 10**(digit - 1)) % 10
            output[count[digit_value] - 1] = array[i]
            count[digit_value] -= 1

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

    max_number = max(array)
    number_of_digits = len(str(max_number))

    for digit in range(1, number_of_digits + 1):
        counting_sort_by_digit(array, digit)

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

C++

#include <iostream>
#include <vector>
#include <algorithm>

void countingSortByDigit(std::vector<int>& array, int digit) {
    int size = array.size();
    std::vector<int> output(size);
    int count[10] = {0};

    for (int i = 0; i < size; i++) {
        int digitValue = (array[i] / digit) % 10;
        count[digitValue]++;
    }

    for (int i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    for (int i = size - 1; i >= 0; i--) {
        int digitValue = (array[i] / digit) % 10;
        output[count[digitValue] - 1] = array[i];
        count[digitValue]--;
    }

    for (int i = 0; i < size; i++) {
        array[i] = output[i];
    }
}

void radixSort(std::vector<int>& array) {
    int maxNumber = *max_element(array.begin(), array.end());
    for (int digit = 1; maxNumber / digit > 0; digit *= 10) {
        countingSortByDigit(array, digit);
    }
}

// Example usage
int main() {
    std::vector<int> arr = {170, 45, 75, 90, 802, 24, 2, 66};
    radixSort(arr);
    for (int num : arr) {
        std::cout << num << " ";
    }
    return 0;
}

Java

import java.util.Arrays;

public class RadixSort {

    public static void radixSort(int[] array) {
        int maxNumber = Arrays.stream(array).max().getAsInt();
        for (int digit = 1; maxNumber / digit > 0; digit *= 10) {
            countingSortByDigit(array, digit);
        }
    }

    private static void countingSortByDigit(int[] array, int digit) {
        int size = array.length;
        int[] output = new int[size];
        int[] count = new int[10];

        for (int i = 0; i < size; i++) {
            int digitValue = (array[i] / digit) % 10;
            count[digitValue]++;
        }

        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        for (int i = size - 1; i >= 0; i--) {
            int digitValue = (array[i] / digit) % 10;
            output[count[digitValue] - 1] = array[i];
            count[digitValue]--;
        }

        for (int i = 0; i < size; i++) {
            array[i] = output[i];
        }
    }

    public static void main(String[] args) {
        int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
        radixSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

Complexity of Radix Sort

• Time Complexity: $O(d⋅(n+k))$
  • $d$: Number of digits in the largest number.
  • $n$: Number of elements in the array.
  • $k$: Range of the digits for decimal system, $k = 10.$
• Space Complexity: $O(n + k)$

Conclusion

Radix sort is a powerful sorting algorithm for integers or fixed-length strings. Its efficiency and non-comparative nature make it a valuable tool for specific use cases, especially where the number of digits or characters is limited. Understanding and implementing radix sort can significantly enhance the performance of sorting operations in such scenarios.