Radix Sort in Java: Sort Numbers Digit by Digit

In this article, we will explore the Radix Sort in Java, understand its logic, implement it, analyze its time and space complexity, discuss its applications, and draw conclusions about its effectiveness.

Table of Contents

Radix Sort Algorithm

Radix Sort is a linear-time sorting algorithm that sorts numbers by considering each digit position individually, from the least significant digit (rightmost) to the most significant digit (leftmost). It relies on the concept of bucketing, where elements are grouped into buckets based on the value of the current digit being considered. The algorithm repeatedly applies this process for each digit position until the entire array is sorted.

Java Implementation

Here is an example of how to implement Radix Sort in Java:

import java.util.Arrays;

public class RadixSort {
    public static void radixSort(int[] arr) {
        // Find the maximum number to determine the number of digits
        int max = Arrays.stream(arr).max().getAsInt();

        // Perform counting sort for every digit position
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSort(arr, 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++) {
            int digit = (arr[i] / exp) % 10;
            count[digit]++;
        }

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

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

        // Copy the output array to the original array
        System.arraycopy(output, 0, arr, 0, n);
    }

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

Output

Sorted array:
2 24 45 66 75 90 170 802

Logical Steps

Below steps are followed for implementation of Radix Sort in Java:

Find the maximum number in the array to determine the number of digits.
Perform counting sort for each digit position from the least significant to the most significant.
In counting sort, count the occurrences of each digit.
Calculate the cumulative count of each digit.
Build the output array by placing each element in the correct position based on the current digit.
Copy the output array back to the original array.

Time Complexity

The time complexity of Radix Sort in Java is O(d * (n + b)), where n is the number of elements, d is the maximum number of digits, and b is the base of the number system. In the case of integers, the base is 10. Radix Sort has a linear time complexity as it iterates through the digits of each element.

Space Complexity

The space complexity of Radix Sort is O(n + b), where n is the number of elements and b is the base of the number system. The additional space is used for the count and output arrays.

Applications

Radix Sort has various applications, including:

Sorting integers or fixed-length strings efficiently.
Finding the longest common prefix in a set of strings.
Radix-based data compression algorithms.
Computer graphics algorithms that require sorting objects based on their attributes.

Whether it’s sorting integers, finding common prefixes, compressing data, or organizing objects in computer graphics, Radix Sort offers an effective solution with its unique approach to sorting by individual digits.

Conclusion: Radix sort in Java

Radix Sort in Java is a non-comparative sorting algorithm that efficiently sorts numbers digit by digit. It provides a linear time complexity, making it suitable for sorting large datasets. Understanding the logic and implementation of Radix Sort in Java equips you with a valuable tool for sorting integers and fixed-length strings. Radix Sort has applications in various domains, including data compression, computer graphics, and string manipulation.