Java Program for Radix Sorting

What is radix sort ?

Radix sort is the generalized bin sort.

Radix sort key idea is to bin sort all the array elements, first on f(k) (the least significant digit, then concentrate bins for the lowest value first, again bin sort on f(k-1) digit and so on.

Make sure each array element is appended to the end of the list, not the beginning.

Radix Sort Algorithm

Sort the array elements using counter range(0 to 9) based on least digit value.

Repeat the sorting for next digits till maximum element number digits.

Radix Sorting Steps

Radix Sorting Time complexity

Radix sorting time complexity is O(N∗logb(N)). here N is the number of elements in the list, b is the base for representing numbers.

Radix Sorting Java Program

import java.util.Scanner;

public class RadixSortingTest{
	public static int max(int[] listVals){		
		int maxVal = listVals[0];
		for(int i=1; i<listVals.length;i++){
			if(maxVal<listVals[i]){
				maxVal = listVals[i];
			}
		}
		return maxVal;
	}
	public static void countingSort(int[] listVals, int n, int place){
		int integerRange = 10;
		int[] freq = new int[integerRange];
		for(int i=0;i<integerRange;i++){
			freq[i] = 0;
		}
		int[] listSorted = new int[n];
		for(int i=0;i<n;i++){
			listSorted[i]=0;
		}
		for(int i=0;i<n;i++){
			freq[(listVals[i]/place)%integerRange] += 1;
		}
		for(int i=1;i<integerRange;i++){
			freq[i] += freq[i-1];
		}
		int i = n-1;
		while(i>=0){
			listSorted[freq[(listVals[i]/place)%10]-1]=listVals[i];
			freq[(listVals[i]/place)%10] -= 1;
			i -= 1;
		}
		for(int j=0;j<n;j++){
			listVals[j] = listSorted[j];
		}
	} 

	public static void radixSort(int[] listVals){
		int n = listVals.length;
		int maxVal = max(listVals);
		int mulVal = 1;
		while(maxVal>0){
			countingSort(listVals, n, mulVal);
			mulVal *= 10;
			maxVal /= 10;
		}
	}
	    
	public static void main(String[] args){
	    int[] numberList, sortedList;
	    Scanner in = new Scanner(System.in); 
	    System.out.println("Radix Sorting");
	    System.out.println("--------------------");
	    System.out.println("Enter numbers count: ");                   
	    int count = in.nextInt();                   
	    numberList = new int[count];
	    System.out.println("Enter numbers: "); 
	    for (int i=0;i<count;i++){
	    	numberList[i]=in.nextInt();
	    }
	    in.close();
	    radixSort(numberList);
	    
	    System.out.println("Sorted numbers: "); 
	    for(int number : numberList){
	    	System.out.print(number+"\t");
	    }
	}
}                                                                                                                                                                                                               

$ javac RadixSortingTest.java
$ java RadixSortingTest 
Radix Sorting
--------------------
Enter numbers count: 
5
Enter numbers: 
2
3
1
5
4
Sorted numbers: 
1	2	3	4	5