Thursday, May 5, 2022

Radix Sort Program in Java

In this post we’ll see how to write Radix sort program in Java. Radix sort is in the league of Counting Sort and Bucket Sort which are O(n) sorting algorithms.

How does Radix sort work

Radix sort works by doing the sorting in passes moving from least significant digit to most significant digit. In each pass you can use any stable sort to sort the numbers on the digit.

If you have an array Arr with the maximum element in array Arr having number of digits as d, then the working of Radix sort is as shown below.

for i = 1 to d
 Use any stable sort (like counting sort)
        to sort Arr on digit d

Following image shows how Radix sort sorts an input array in each pass. Here the maximum number is 655 so number of passes is 3.

radix sort in Java

Radix Sort Java program

Java program for Radix sort works on the following logic.

  1. Find the maximum number in the input array.
  2. Loop to iterate each digit of the maximum number starting from the least significant digit.
  3. Sort the array on that digit using Counting sort.
public class RadixSort {

  public static void main(String[] args) {
    int[] arr = {80, 406, 21, 655, 55, 4, 8, 91, 87, 6};
    System.out.println("Original Array- " + Arrays.toString(arr));
    radixSort(arr);
    System.out.println("Sorted array after Radix sort- " + Arrays.toString(arr));
  }
    
  private static void radixSort(int[] arr){
    int max = getMaxElement(arr);
    int position = 1;
    while(max/position > 0){
      countingSort(arr, position);
      position *= 10;
    }        
  }
        
  private static int getMaxElement(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 countingSort(int[] arr, int position){
    int n = arr.length;
    int[] output = new int[n];
    int[] count = new int[n];
      
    //count number of times each element appear
    for(int i = 0; i < arr.length; i++){
      count[(arr[i]/position)%10]++;
    }

    // each element stores (element at current index+element
    // at previous index) to get the actual position of the element
    for(int i = 1; i < n; i++){
      count[i] = count[i] + count[i-1];
    }
  
    // for correct placement of the numbers start from the end
    for(int i = n-1; i >=0; i--){
      output[count[(arr[i]/position)%10] - 1] = arr[i];
      count[(arr[i]/position)%10]--;
    }
    // Copy output array to input to the input for 
    // the next stage of counting sort
    for(int i = 0; i < output.length; i++){
      arr[i] = output[i];
    }
    System.out.println("Counting sort at this stage " + Arrays.toString(arr));
  }
}

Output

Original Array- [80, 406, 21, 655, 55, 4, 8, 91, 87, 6]
Counting sort at this stage [80, 21, 91, 4, 655, 55, 406, 6, 87, 8]
Counting sort at this stage [4, 406, 6, 8, 21, 655, 55, 80, 87, 91]
Counting sort at this stage [4, 6, 8, 21, 55, 80, 87, 91, 406, 655]
Sorted array after Radix sort- [4, 6, 8, 21, 55, 80, 87, 91, 406, 655]

Performance of Radix Sort

If you are using Counting sort for sorting in each pass of Radix sort then time complexity of Radix sort is O(d*(n+k)). Here O(n+k) is the time complexity of counting sort and d is the number of passes over number having d digits.

Auxiliary space requirement is (n+k). Count array takes k space and the output array of the same size as input array is also used while sorting. Thus the space complexity of Radix sort is O(n+k).

That's all for this topic Radix Sort Program in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page


Related Topics

  1. Bubble Sort Program in Java
  2. Quick Sort Program in Java
  3. Heap Sort Program in Java
  4. Java Program to Create Your Own BlockingQueue
  5. Java Program to Reverse a Number

You may also like-

  1. Reading File in Java Using Files.lines And Files.newBufferedReader
  2. How to Create PDF in Java Using OpenPDF
  3. Converting String to Enum Type in Java
  4. Java Program to Get All The Tables in a DB Schema
  5. Just In Time Compiler (JIT) in Java
  6. Reflection in Java - Getting Class Information
  7. String Vs StringBuffer Vs StringBuilder in Java
  8. Replica Placement Policy in Hadoop Framework

2 comments:

  1. Hi I tried to excute same program, but final result is not sorted properly. Wanted to clarify whether Radix Sort doesnt give consistent results for same set of input.

    Code :
    package Trees.src.com.cracking.Sorting;

    import java.util.Arrays;

    public class RadixSort {

    public static void main(String[] args){
    int[] array = {80, 406, 21, 655, 55, 4, 8, 91, 87, 6};
    int max = getMaxElement(array);
    System.out.println(max);
    int position = 1;
    while(max/position > 0)
    {countingSort(array,position);position = position * 10;}
    }

    public static int getMaxElement(int arr[]){
    int max = arr[0];
    for(int i=1;i max)
    max = arr[i];
    return max;
    }

    //counting sort but sort at each position
    public static void countingSort(int[] arr,int position){
    int[] count = new int[arr.length];
    int[] output = new int[arr.length];

    for(int i=0;i<arr.length;i++)
    count[(arr[i]/position)%10]++;

    for(int i=1;i<count.length;i++)
    count[i] = count[i] + count[i-1];

    for(int i=0;i<arr.length;i++)
    {
    output[count[(arr[i]/position)%10] - 1] = arr[i];count[(arr[i]/position)%10]--;
    }

    for(int i=0;i<arr.length;i++)
    arr[i] = output[i];

    System.out.println(Arrays.toString(arr));
    }
    }

    ReplyDelete
    Replies
    1. Just have a look at your getMaxElement() method, how are you calculating max element there? Shouldn't there be a if condition to check if next element is greater than the current?

      Delete