Sorting is one of the most important topics in programming, and understanding efficient sorting algorithms can make your applications faster and more reliable. Radix Sort is a fascinating sorting technique, particularly useful for large sets of numbers. Unlike traditional comparison-based algorithms like Quick Sort or Merge Sort, Radix Sort sorts numbers digit by digit. This approach makes it especially efficient when working with large datasets or numbers with a fixed number of digits.
with hands-on learning.
get the skills and confidence to land your next move.
Radix Sort is widely used in applications such as data processing, digital systems, and computer graphics where quick organization of numeric data is needed. For beginners, implementing Radix Sort provides a great opportunity to understand non-comparative sorting techniques. The algorithm works by first sorting numbers based on the least significant digit and progressively moves to the most significant digit, ensuring stability at each step. By exploring Radix Sort in Java, you also get hands-on experience with arrays, loops, and helper functions, which strengthens your core programming skills.
Program 1: Basic Radix Sort Using Least Significant Digit
This program demonstrates the standard Radix Sort approach using the least significant digit (LSD) first. It sorts an array of integers by processing one digit at a time from right to left.
public class RadixSortLSD {
public static void radixSort(int[] arr) {
int max = arr[0];
for (int num : arr) if (num > max) max = num;
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSortByDigit(arr, exp);
}
}
public static void countingSortByDigit(int[] arr, int exp) {
int n = arr.length;
int[] output = new int[n];
int[] count = new int[10];
for (int i = 0; i < n; i++)
count[(arr[i] / exp) % 10]++;
for (int i = 1; i < 10; i++)
count[i] += count[i - 1];
for (int i = n - 1; i >= 0; i--) {
int index = (arr[i] / exp) % 10;
output[count[index] - 1] = arr[i];
count[index]--;
}
System.arraycopy(output, 0, arr, 0, n);
}
public static void main(String[] args) {
int[] numbers = {170, 45, 75, 90, 802, 24, 2, 66};
System.out.println("Original Array:");
for (int num : numbers) System.out.print(num + " ");
System.out.println();
radixSort(numbers);
System.out.println("Sorted Array:");
for (int num : numbers) System.out.print(num + " ");
}
}This program uses a counting sort on each digit, ensuring that numbers are sorted starting from the least significant digit. Beginners can understand how breaking down numbers digit by digit simplifies the sorting process and maintains stability.
Program 2: Radix Sort Using Most Significant Digit
Radix Sort can also start from the most significant digit (MSD) for a recursive approach. This program demonstrates how sorting from the highest place value down can organize the array efficiently.
import java.util.ArrayList;
public class RadixSortMSD {
public static void radixSortMSD(int[] arr, int exp) {
if (arr.length <= 1 || exp == 0) return;
@SuppressWarnings("unchecked")
ArrayList<Integer>[] buckets = (ArrayList<Integer>[]) new ArrayList[10];
for (int i = 0; i < 10; i++) {
buckets[i] = new ArrayList<>();
}
for (int number : arr) {
int index = (number / exp) % 10;
buckets[index].add(number);
}
int i = 0;
for (ArrayList<Integer> bucket : buckets) {
int[] temp = bucket.stream().mapToInt(Integer::intValue).toArray();
radixSortMSD(temp, exp / 10);
for (int num : temp) arr[i++] = num;
}
}
public static void main(String[] args) {
int[] numbers = {170, 45, 75, 90, 802, 24, 2, 66};
int max = numbers[0];
for (int num : numbers) if (num > max) max = num;
int exp = 1;
while (max / exp >= 10) exp *= 10;
System.out.println("Original Array:");
for (int num : numbers) System.out.print(num + " ");
System.out.println();
radixSortMSD(numbers, exp);
System.out.println("Sorted Array:");
for (int num : numbers) System.out.print(num + " ");
}
}This MSD approach uses recursion to sort numbers based on their most significant digits first. Beginners can see how recursion helps divide and conquer, processing each subset efficiently.
Program 3: Radix Sort Handling Negative Numbers
Standard Radix Sort only works with positive integers. This program demonstrates how to sort an array containing both positive and negative numbers.
import java.util.ArrayList;
import java.util.List;
public class RadixSortWithNegatives {
public static void radixSort(int[] arr) {
List<Integer> positives = new ArrayList<>();
List<Integer> negatives = new ArrayList<>();
for (int num : arr) {
if (num >= 0) positives.add(num);
else negatives.add(-num);
}
int[] posArr = positives.stream().mapToInt(Integer::intValue).toArray();
int[] negArr = negatives.stream().mapToInt(Integer::intValue).toArray();
RadixSortLSD.radixSort(posArr);
RadixSortLSD.radixSort(negArr);
int index = 0;
for (int i = negArr.length - 1; i >= 0; i--) arr[index++] = -negArr[i];
for (int num : posArr) arr[index++] = num;
}
public static void main(String[] args) {
int[] numbers = {170, -45, 75, -90, 802, 24, -2, 66};
System.out.println("Original Array:");
for (int num : numbers) System.out.print(num + " ");
System.out.println();
radixSort(numbers);
System.out.println("Sorted Array:");
for (int num : numbers) System.out.print(num + " ");
}
}
class RadixSortLSD {
public static void radixSort(int[] arr) {
int max = arr[0];
for (int num : arr) if (num > max) max = num;
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSortByDigit(arr, exp);
}
}
public static void countingSortByDigit(int[] arr, int exp) {
int n = arr.length;
int[] output = new int[n];
int[] count = new int[10];
for (int i = 0; i < n; i++)
count[(arr[i] / exp) % 10]++;
for (int i = 1; i < 10; i++)
count[i] += count[i - 1];
for (int i = n - 1; i >= 0; i--) {
int index = (arr[i] / exp) % 10;
output[count[index] - 1] = arr[i];
count[index]--;
}
System.arraycopy(output, 0, arr, 0, n);
}
}This program separates negative and positive numbers, sorts them individually, and recombines them. Beginners can understand that small transformations allow algorithms to handle a wider range of inputs efficiently.
Program 4: Radix Sort Using Buckets
Radix Sort can also be implemented using dynamic buckets instead of counting arrays. This method simplifies visualization and teaches beginners about grouping and combining data.
import java.util.ArrayList;
import java.util.List;
public class RadixSortBuckets {
public static void radixSort(int[] arr) {
int max = arr[0];
for (int num : arr) if (num > max) max = num;
int exp = 1;
while (max / exp > 0) {
List<List<Integer>> buckets = new ArrayList<>();
for (int i = 0; i < 10; i++) buckets.add(new ArrayList<>());
for (int num : arr) {
int index = (num / exp) % 10;
buckets.get(index).add(num);
}
int idx = 0;
for (List<Integer> bucket : buckets) {
for (int num : bucket) arr[idx++] = num;
}
exp *= 10;
}
}
public static void main(String[] args) {
int[] numbers = {170, 45, 75, 90, 802, 24, 2, 66};
System.out.println("Original Array:");
for (int num : numbers) System.out.print(num + " ");
System.out.println();
radixSort(numbers);
System.out.println("Sorted Array:");
for (int num : numbers) System.out.print(num + " ");
}
}Using buckets demonstrates a visual and intuitive way of grouping numbers by digits. Beginners can see how Radix Sort organizes data step by step, making it easier to follow.
Program 5: Radix Sort for String Numbers
Radix Sort can also sort string representations of numbers efficiently. This is useful in data processing scenarios where numbers are stored as text.
import java.util.ArrayList;
import java.util.List;
public class RadixSortStrings {
public static void radixSort(String[] arr) {
int maxLength = 0;
for (String s : arr) if (s.length() > maxLength) maxLength = s.length();
// Pad all strings with leading zeros for proper comparison
for (int i = 0; i < arr.length; i++) {
arr[i] = String.format("%" + maxLength + "s", arr[i]).replace(' ', '0');
}
for (int i = maxLength - 1; i >= 0; i--) {
List<List<String>> buckets = new ArrayList<>();
for (int j = 0; j < 10; j++) buckets.add(new ArrayList<>());
for (String number : arr) {
int digit = number.charAt(i) - '0';
buckets.get(digit).add(number);
}
int idx = 0;
for (List<String> bucket : buckets) {
for (String number : bucket) arr[idx++] = number;
}
}
}
public static void main(String[] args) {
String[] numbers = {"170", "45", "75", "90", "802", "24", "2", "66"};
System.out.println("Original Array:");
for (String num : numbers) System.out.print(num + " ");
System.out.println();
radixSort(numbers);
System.out.println("Sorted Array:");
for (String num : numbers) System.out.print(Integer.parseInt(num) + " ");
}
}By padding each number with leading zeros, all strings become the same length, allowing accurate digit-by-digit comparison.
This ensures correct numerical ordering even when the strings have different lengths.
Frequently Asked Questions (FAQ)
Radix Sort is a powerful algorithm but raises some questions for beginners. Here are some answers.
Q1: What is the time complexity of Radix Sort?
Radix Sort has O(nk) complexity, where n is the number of elements and k is the number of digits in the largest number.
Q2: Is Radix Sort stable?
Yes, Radix Sort is stable, meaning equal elements maintain their original order.
Q3: Can Radix Sort handle negative numbers?
Yes, by separating negatives and positives, then sorting and recombining, it can handle negative values.
Q4: When should I use Radix Sort?
Radix Sort is best for large datasets of integers or fixed-length strings where comparisons are costly.
Q5: Can Radix Sort be used for strings?
Yes, it can sort string representations of numbers or other fixed-length textual sequences efficiently.
Conclusion
Radix Sort is a versatile and efficient sorting algorithm that goes beyond traditional comparison-based methods. In this article, we explored multiple implementations, including LSD and MSD approaches, handling negative numbers, bucket-based sorting, and sorting strings.
For beginners, practicing Radix Sort helps improve array manipulation, recursion understanding, and logical thinking. By experimenting with different types of data and approaches, you can develop a strong foundation for efficiently handling large datasets in Java.
