Java Radix Sort Algorithm

1. Radix Sort Algorithm
2. Radix Sort Algorithm Implementation in Java

In Radix Sort, the elements are sorted by first grouping the individual numbers of the same place value and then sorted according to the ascending or descending order. This tutorial explains the radix sort algorithm in detail and demonstrates the implementation of radix sort in Java.

Radix Sort Algorithm

Follow the steps below to apply the radix sort.

1. First of all, find the maximum element from the input array; that maximum number will then be used to go through the significant places of all array members.
2. Next, go through each significant place one by one. We can use any stable sorting algorithm, for example, the counting sort, to sort the elements of each significant place.

Support an array of six elements. The radix sort will first sort the elements based on the values of the unit place.

Then sorts the elements of the array based on the value of the tenth place.

Suppose the array is [9, 50, 4, 203, 17, 39]. The picture below shows this array sorted according to the radix sort with multiple passes.

Time Complexity of Radix Sort Algorithm

The table below shows the time complexity of the radix sort algorithm in different cases.

1. Best Case - When no sorting is required, the array is already sorted. In the Best case scenario, the radix sort time complexity is Ω(n+k).
2. Average Case - The array elements are in a chaotic order, not properly descending or ascending order. The Radix Sort time complexity is θ(nk) in the average case scenario.
3. Worst-Case - When the array elements must be sorted in reverse order, for example, from ascending to descending or descending to ascending order. The Radix Sort time complexity is O(nk) in the worst-case scenario.

Pseudo Code of Radix Sort Algorithm

The Pseudo Code for the Radix Sort algorithm is given below.

Radix_Sort(Input_Array)
    MAX = largest number in the input array
    DIGIT = number of digits in the largest number
    Now, create DIGIT buckets of size 0 - 9
    for x -> 0 to DIGIT
        sort the elements according to any stable sort

Radix Sort Algorithm Implementation in Java

Using the counting sort, let’s implement the radix sort algorithm. See example:

package delftstack;

import java.util.Arrays;

public class Radix_Sort {
  public static void main(String args[]) {
    int[] input_array = {9, 50, 4, 203, 17, 39};
    int array_size = input_array.length;
    Radix_Sort RadixSort = new Radix_Sort();
    RadixSort.Radix_Sort(input_array, array_size);
    System.out.println("Sorted Array Using Radix Sort: ");
    System.out.println(Arrays.toString(input_array));
  }

  // Counting sort to sort the elements on the basis of significant places
  void Counting_Sort(int input_array[], int array_size, int number_place) {
    int[] output_array = new int[array_size + 1];
    int max_number = input_array[0];
    for (int x = 1; x < array_size; x++) {
      if (input_array[x] > max_number) {
        max_number = input_array[x];
      }
    }
    int[] count_array = new int[max_number + 1];

    for (int x = 0; x < max_number; ++x) {
      count_array[x] = 0;
    }
    // Calculating the count of elements
    for (int x = 0; x < array_size; x++) {
      count_array[(input_array[x] / number_place) % 10]++;
    }
    // Calculating the cumulative count
    for (int x = 1; x < 10; x++) {
      count_array[x] += count_array[x - 1];
    }
    // Sorting the elements
    for (int x = array_size - 1; x >= 0; x--) {
      output_array[count_array[(input_array[x] / number_place) % 10] - 1] = input_array[x];
      count_array[(input_array[x] / number_place) % 10]--;
    }

    for (int x = 0; x < array_size; x++) {
      input_array[x] = output_array[x];
    }
  }

  // Get the largest element from input array
  int Get_Max(int input_array[], int array_size) {
    int max_number = input_array[0];
    for (int i = 1; i < array_size; i++) {
      if (input_array[i] > max_number) {
        max_number = input_array[i];
      }
    }
    return max_number;
  }

  // Implement the radix sort
  void Radix_Sort(int input_array[], int array_size) {
    // Get the maximum number
    int max_number = Get_Max(input_array, array_size);

    // Apply the counting sort based on significant place value.
    for (int number_place = 1; max_number / number_place > 0; number_place *= 10) {
      Counting_Sort(input_array, array_size, number_place);
    }
  }
}

The code above implements the radix sort with the help of the counting sort. See output:

Sorted Array Using Radix Sort:
[4, 9, 17, 39, 50, 203]