Radix Sort in Java

Radix Sort in Java

Radix Sort is similar to a register algorithm which we use in day to day work while arranging a list of names, in alphabetical order, in that similar way rad ix sort arranges the given numbers by arranging them in the order of each digit sequentially starting from one’s place and moving to ten’s or hundred’s place depending upon the given data.

Radix Sort in Java


We have comparison based sorting algorithms for fairly large data sets, we have counting sort for n elements, for faster linear sorting, but the problem arises when the data set of of order n2, this is where Radix Sort comes into play.                                

  • The algorithm works counter-intuitively by sorting on the least significant digits first.
  • If we have log2n bits for every digit, the running time of Radix appears to be better than Quick Sort for a wide range of input numbers. 
Java Program for radix sort

Code For Radix Sort in Java

//Radix sort Java implementation 
import java.io.*; 
import java.util.*;

class PrepInsta 
			/*Main Method to check for above function*/
		>public static void main (String[] args) 
			int a[] = {17, 45, 75, 90, 82, 24, 12, 60}; 
			int len = a.length; 

	// A utility function to get maximum value in a[] 
	static int getMax(int a[], int n) 
		int mx = a[0]; 
		for (int i = 1; i < len; i++) 
			if (a[i] > mx) 
				mx = a[i]; 
		return mx; 

	// A function to do counting sort of arr[] according to 
	// the digit represented by exp. 
	static void countSort(int a[], int len, int exp) 
		int output[] = new int[len]; // output array 
		int i; 
		int count[] = new int[10]; 

		// Store count of occurrences in count[] 
		for (i = 0; i < len; i++) 
			count[ (a[i]/exp)%10 ]++; 

		// Change count[i] so that count[i] now contains 
		// actual position of this digit in output[] 
		for (i = 1; i < 10; i++) 
			count[i] += count[i - 1]; 

		// Build the output array 
		for (i = len - 1; i >= 0; i--) 
			output[count[ (a[i]/exp)%10 ] - 1] = a[i]; 
			count[ (a[i]/exp)%10 ]--; 

		// Copy the output array to arr[], so that arr[] now 
		// contains sorted numbers according to curent digit 
		for (i = 0; i < len; i++) 
			a[i] = output[i]; 

	// The main function to that sorts arr[] of size n using 
	// Radix Sort 
	static void radixsort(int a[], int len) 
		// Find the maximum number to know number of digits 
		int m = getMax(a, len); 

		// Do counting sort for every digit. Note that instead 
		// of passing digit number, exp is passed. exp is 10^i 
		// where i is current digit number 
		for (int exp = 1; m/exp > 0; exp *= 10) 
			countSort(a, len, exp); 

	// A utility function to print an array 
	static void print(int a[], int len) 
		for (int i=0; i<len; i++) 
			System.out.print(a[i]+" ");