Radix Sort Algorithm in Java

1. Introduction

Radix Sort is a non-comparative sorting algorithm that works by distributing elements of an array into buckets according to their individual digits. It processes the digits of each number one at a time, from the least significant digit (LSD) to the most significant digit (MSD) or vice-versa. The algorithm is particularly efficient when the range of numbers in the input is significantly larger than the number of input numbers.

2. Implementation Steps

1. Determine the maximum number in the array to know the number of digits.

2. Loop from the least significant digit to the most significant digit.

3. For each digit, sort numbers using counting sort as a subroutine.

4. Return the sorted numbers.

3. Implementation in Java

public class RadixSort {
    public static void sort(int[] arr) {
        // Find the maximum number to know the number of digits
        int max = getMax(arr);
        // Do counting sort for every digit
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSortByDigit(arr, exp);
        }
    }
    private static int getMax(int[] arr) {
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        return max;
    }
    private static void countingSortByDigit(int[] arr, int exp) {
        int n = arr.length;
        int[] output = new int[n];
        int[] count = new int[10];
        // Initialize count array
        for (int i = 0; i < n; i++) {
            count[(arr[i] / exp) % 10]++;
        }
        // Change count[i] so that count[i] contains 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 based on current digit
        System.arraycopy(output, 0, arr, 0, n);
    }
    public static void main(String[] args) {
        int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
        System.out.println("Original array:");
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
        sort(arr);
        System.out.println("Sorted array:");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

Output:

Original array:
170 45 75 90 802 24 2 66
Sorted array:
2 24 45 66 75 90 170 802

Explanation:

1. First, determine the maximum number in the array to know the maximum number of digits using the getMax function.

2. Sort numbers based on every digit, starting from the least significant digit (LSD) to the most significant digit (MSD) using a loop.

3. Use the countingSortByDigit function as a subroutine to sort the numbers based on each individual digit.

4. The sorted values are then copied back to the original array.