Radix Sort Explanation

Radix Sort is a non-comparative sorting algorithm that sorts numbers by processing individual digits. It works by grouping numbers based on their individual digits from the least significant digit (LSD) to the most significant digit (MSD). Radix Sort is particularly efficient for sorting large datasets of integers and is often faster than comparison-based algorithms.

Algorithm Steps:

1. Identify the maximum number in the array to determine the number of digits.
2. Iterate through each digit (starting from the least significant digit to the most significant).
3. Use a stable sorting algorithm (commonly Counting Sort) to sort the numbers based on the current digit.
4. Repeat for all digits until the entire array is sorted.

Advantages:

• 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 input (for counting sort).
• It can be more efficient than comparison-based sorting algorithms like Quick Sort or Merge Sort for large datasets.
• Works well with fixed-size integer keys.

Disadvantages:

• Radix Sort requires additional space for the stable sorting algorithm used (like Counting Sort).
• Not suitable for floating-point numbers or strings without modifications.
• Performance can degrade with a larger range of input numbers.

Code Examples

C++ Code:

#include <iostream>
#include <vector>
using namespace std;

// A function to do counting sort based on the digit represented by exp.
void countingSort(vector<int>& arr, int exp) {
    int n = arr.size();
    vector<int> output(n); // output array
    int count[10] = {0};

    // Count occurrences of each digit
    for (int i = 0; i < n; i++) {
        count[(arr[i] / exp) % 10]++;
    }

    // Change count[i] so that count[i] contains the actual position of this digit in output[]
    for (int i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    // Build the output array
    for (int i = n - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }

    // Copy the output array to arr[] so that arr[] contains sorted numbers
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

// The main function that sorts 'arr' using Radix Sort
void radixSort(vector<int>& arr) {
    int maxVal = *max_element(arr.begin(), arr.end());

    // Apply counting sort to sort elements based on place value.
    for (int exp = 1; maxVal / exp > 0; exp *= 10) {
        countingSort(arr, exp);
    }
}

int main() {
    vector<int> arr = {170, 45, 75, 90, 802, 24, 2, 66};
    radixSort(arr);
    cout << "Sorted array: \n";
    for (int num : arr) {
        cout << num << " ";
    }
    return 0;
}

Java Code:

import java.util.Arrays;

public class RadixSort {
    // A function to do counting sort based on the digit represented by exp.
    public static void countingSort(int[] arr, int exp) {
        int n = arr.length;
        int[] output = new int[n];
        int[] count = new int[10];

        // Count occurrences of each digit
        for (int i = 0; i < n; i++) {
            count[(arr[i] / exp) % 10]++;
        }

        // Change count[i] so that count[i] contains the actual position of this digit in output[]
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        // Build the output array
        for (int i = n - 1; i >= 0; i--) {
            output[count[(arr[i] / exp) % 10] - 1] = arr[i];
            count[(arr[i] / exp) % 10]--;
        }

        // Copy the output array to arr[] so that arr[] contains sorted numbers
        System.arraycopy(output, 0, arr, 0, n);
    }

    // The main function that sorts 'arr' using Radix Sort
    public static void radixSort(int[] arr) {
        int maxVal = Arrays.stream(arr).max().getAsInt();

        // Apply counting sort to sort elements based on place value.
        for (int exp = 1; maxVal / exp > 0; exp *= 10) {
            countingSort(arr, exp);
        }
    }

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

Python Code:

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

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

    # Change count[i] so that count[i] contains the actual position of this digit in output[]
    for i in range(1, 10):
        count[i] += count[i - 1]

    # Build the output array
    for i in range(n - 1, -1, -1):
        index = (arr[i] // exp) % 10
        output[count[index] - 1] = arr[i]
        count[index] -= 1

    # Copy the output array to arr[]
    for i in range(n):
        arr[i] = output[i]

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

    # Apply counting sort to sort elements based on place value.
    exp = 1
    while max_val // exp > 0:
        counting_sort(arr, exp)
        exp *= 10

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

Time Complexity:

• Best case: O(n⋅k)
• Average case: O(n⋅k)
• Worst case: O(n⋅k)

Where n is the number of elements and k is the range of the input values (number of digits in the largest number).

Radix Sort is particularly useful for sorting large sets of integers or fixed-length strings, and it can outperform traditional comparison-based algorithms when dealing with such datasets.