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.