How to write a Radix sort program in Java

In this post, we will learn How to write a Radix sort program in Java. Radix sort is in the group of Counting Sort and Bucket Sort which are O(n) sorting algorithms.

How does Radix sort work?

The radix sort usually works by doing the sorting in passes moving from least significant digit to the most significant digit. In each pass, we can use any stable sort to sort the numbers on the digit.

If you have an array inputArr with the maximum element in array inputArr having a 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 inputArr on digit d

Steps to writing Radix sort is as follows.

First of all, find the maximum number in the input array.
Afterward, we have to loop to iterate each digit of the maximum number starting from the least significant digit.
Finally, sort the array on that digit using Counting sort.

Compete Source Code:

package com.kkjavatutorials.client;

import java.util.Arrays;
/**
 * Java program for Radix sorting
 * @author KK JavaTutorials
 */
public class RadixSortTest {

    public static void main(String[] args) {
    	
    	//Input Array
        int[] inputArr = {90, 106, 45, 91, 56, 40, 109, 201, 9, 100};
        System.out.println("Original Input Array: " + Arrays.toString(inputArr));
        
        //Call for sorting using Radix Sorting
        radixSort(inputArr);
        
        //Print sorted Array
        System.out.println("Array Sorted Using Radix sort: " + Arrays.toString(inputArr));
    }
    
    private static void radixSort(int[] inputArr){
    	
        int maxElement = getMaxElementFromInputArray(inputArr);
        int position = 1;
        
        while(maxElement/position > 0){
            countingSort(inputArr, position);
            position = position * 10;
        }        
    }
      
    //Getting Max element form input array
    private static int getMaxElementFromInputArray(int[] inputArr){
        int maxElement = inputArr[0];
        for(int i = 1; i < inputArr.length; i++){
            if (inputArr[i] > maxElement){
                maxElement = inputArr[i];
            }
        }
        return maxElement;
    }
    
    private static void countingSort(int[] inputArr, int position){
    	
        int inputArrayLength = inputArr.length;
        int[] outputArr = new int[inputArrayLength];
        int[] countArr = new int[inputArrayLength];
        
        /*Counting number of times each element
         appear in input array*/
        for(int i = 0; i < inputArr.length; i++){
            countArr[(inputArr[i]/position)%10]++;
        }

       /* Here we have store each element[element at current index+element
        at previous index] to get the actual position of the element*/
        for(int i = 1; i < inputArrayLength; i++){
            countArr[i] = countArr[i] + countArr[i-1];
        }
    
        /*To get correct placement of the numbers
         start from the end */
        for(int i = inputArrayLength-1; i >=0; i--){
            outputArr[countArr[(inputArr[i]/position)%10] - 1] = inputArr[i];
            countArr[(inputArr[i]/position)%10]--;
        }
        
        /*Copy output array to input to the input for 
        the next stage of counting sort */
        for(int i = 0; i < outputArr.length; i++){
            inputArr[i] = outputArr[i];
        }
    }
}

package com.kkjavatutorials.client;

import java.util.Arrays;

/**

* Java program for Radix sorting

* @author KK JavaTutorials

public class RadixSortTest {

public static void main(String[] args) {

//Input Array

int[] inputArr = {90, 106, 45, 91, 56, 40, 109, 201, 9, 100};

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

//Call for sorting using Radix Sorting

radixSort(inputArr);

//Print sorted Array

System.out.println("Array Sorted Using Radix sort: " + Arrays.toString(inputArr));

}

private static void radixSort(int[] inputArr){

int maxElement = getMaxElementFromInputArray(inputArr);

int position = 1;

while(maxElement/position > 0){

countingSort(inputArr, position);

position = position * 10;

}

//Getting Max element form input array

private static int getMaxElementFromInputArray(int[] inputArr){

int maxElement = inputArr[0];

for(int i = 1; i < inputArr.length; i++){

if (inputArr[i] > maxElement){

maxElement = inputArr[i];

}

return maxElement;

}

private static void countingSort(int[] inputArr, int position){

int inputArrayLength = inputArr.length;

int[] outputArr = new int[inputArrayLength];

int[] countArr = new int[inputArrayLength];

/*Counting number of times each element

appear in input array*/

for(int i = 0; i < inputArr.length; i++){

countArr[(inputArr[i]/position)%10]++;

}

/* Here we have store each element[element at current index+element

at previous index] to get the actual position of the element*/

for(int i = 1; i < inputArrayLength; i++){

countArr[i] = countArr[i] + countArr[i-1];

}

/*To get correct placement of the numbers

start from the end */

for(int i = inputArrayLength-1; i >=0; i--){

outputArr[countArr[(inputArr[i]/position)%10] - 1] = inputArr[i];

countArr[(inputArr[i]/position)%10]--;

}

/*Copy output array to input to the input for

the next stage of counting sort */

for(int i = 0; i < outputArr.length; i++){

inputArr[i] = outputArr[i];

}

The Output of this program:

Original Input Array: [90, 106, 45, 91, 56, 40, 109, 201, 9, 100]
Array Sorted Using Radix sort: [9, 40, 45, 56, 90, 91, 100, 106, 109, 201]

Performance of Radix Sort:

If We are using Counting sort for sorting in each pass of Radix sort then the 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.

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

You May Also Like:

What is Sorting and why is Sorting Necessary?
Classification of Sorting Algorithms
Java program for Bubble Sort using Iterative Approach
Java program for Bubble Sort using recursive Approach
How to Write a Java program for Selection Sort in Java
How to Write a Java program for Insertion Sort in java?
How to write Merge sort program in Java ?
Tree Sort Using Binary Search Tree in Java

That’s all about How to write a Radix sort program in Java?
If you have any feedback or suggestion please feel free to drop in below comment box.

Leave a Reply Cancel reply