Radix Sort Implementation in Java

By
Shivam Gupta
-
24
Radix Sort Implementation in Java
Advertisement

Radix Sort Implementation in Java

Radix Sort is a fascinating algorithm that sorts elements based on individual digits, making it particularly useful for integers. In this blog post, we will explore the implementation of Radix Sort in Java, providing a detailed explanation and illustrative examples.

Overview

Radix Sort processes elements digit by digit, from the least significant digit (LSD) to the most significant digit (MSD) or vice versa. It’s a non-comparative sorting algorithm that exploits the structure of numeric data. Radix Sort is often employed when the range of possible values is known and small, allowing for efficient bucketing and sorting.

Here’s a step-by-step explanation of how Radix Sort works:

  1. Least Significant Digit (LSD) Radix Sort:
    • The algorithm starts by sorting elements based on their least significant digit.
    • After the first pass, the elements are partially sorted based on the rightmost digit.
  2. Intermediate Passes:
    • Radix Sort continues with additional passes, each time sorting based on the next significant digit towards the most significant digit.
    • The process iterates until the entire number or string is considered.
  3. Most Significant Digit (MSD) Radix Sort:
    • The final pass considers the most significant digit, resulting in a fully sorted array.
  4. Bucketing or Counting Sort:
    • At each pass, Radix Sort uses a stable sorting algorithm, often a variant of counting sort, to distribute elements into buckets based on the digit being considered.
    • Elements within each bucket are then collected to form the sorted array.
  5. Complexity:
    • Radix Sort has a time complexity of O(nk), where n is the number of elements and k is the maximum number of digits in the input.
  6. Stable Sorting:
    • Radix Sort is inherently stable, meaning that the relative order of equal elements is preserved throughout the sorting process.

Java Implementation

Let’s delve into a Java implementation of Radix Sort:

Java Program – Radix Sort
import java.util.Arrays;

public class RadixSort{

    public static void main(String[] args) {
        int[] array = {170, 45, 75, 90, 802, 24, 2, 66};

        System.out.println("Original Array: " + Arrays.toString(array));

        // Call the sort method to perform Radix Sort
        sort(array);

        System.out.println("Sorted Array: " + Arrays.toString(array));
    }

    public static void sort(int[] array) {
        // Find the maximum number to determine the number of digits
        int max = Arrays.stream(array).max().orElse(0);
        int exp = 1;

        while (max / exp > 0) {
            countingSort(array, exp);
            exp *= 10;
        }
    }

    public static void countingSort(int[] array, int exp) {
        int n = array.length;
        int[] output = new int[n];
        int[] count = new int[10];

        // Initialize the counting array
        Arrays.fill(count, 0);

        // Count occurrences of each digit at the current place value
        for (int i : array) {
            count[(i / exp) % 10]++;
        }

        // Update the counting array to represent cumulative count
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

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

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

Walkthrough of the Implementation

  1. Main Radix Sort Method:
  • The sort method initiates the Radix Sort process by finding the maximum number and iterating through each digit place value.
  1. Counting Sort Method:
  • The countingSort method performs counting sort for each digit place value.
  • It counts occurrences, updates the counting array for cumulative counts, and builds the output array.

Example

Consider an example array: {170, 45, 75, 90, 802, 24, 2, 66}.

  1. First Iteration (Least Significant Digit):
  • Sorting by the least significant digit (1’s place): {170, 90, 802, 2, 24, 45, 75, 66}.
  1. Second Iteration (Next Significant Digit):
  • Sorting by the next significant digit (10’s place): {802, 2, 24, 45, 66, 170, 75, 90}.
  1. Third Iteration (Most Significant Digit):
  • Sorting by the most significant digit (100’s place): {2, 24, 45, 66, 75, 90, 170, 802}.

Output:

Output – Radix Sort
Original Array: [170, 45, 75, 90, 802, 24, 2, 66]
Sorted Array: [2, 24, 45, 66, 75, 90, 170, 802]

Complexity

ComplexityBest CaseAverage CaseWorst Case
Time ComplexityO(nk)O(nk)O(nk)
Space ComplexityO(n + k)O(n + k)O(n + k)

Explanation:

  1. Time Complexity:
    • Best Case: O(nk) – Occurs when the number of digits (k) is small, and the elements are evenly distributed across buckets.
    • Average Case: O(nk) – Remains the same as the best case since Radix Sort’s time complexity is dominated by the number of digits.
    • Worst Case: O(nk) – Even in the worst case, Radix Sort maintains its linear time complexity, making it efficient for various scenarios.
  2. Space Complexity:
    • O(n + k) – The space complexity is determined by the size of the input array (n) and the range of values (k). It includes the auxiliary space used for counting sort and creating buckets.

Conclusion

Radix Sort’s unique approach to sorting by digits provides efficiency, especially for integers. Understanding its implementation in Java opens the door to utilizing this algorithm in scenarios where its linear time complexity shines.

Latest Posts:

RELATED ARTICLESMORE FROM AUTHOR