Radix Sort Java Program and Algorithm

This tutorial is about radix sort java program and algorithm.

Here is a very basic and detailed description of algorithm that we follow to implement the radix sort in java. We mostly rely on the place value of digits to sort it out in the given list. So, our first basic task is to find out the number with maximum length and then iterate the whole loop over the length of the digit.

Next we arrange every number considering 1s place value, 10s place value, 100s place value and so on till the length of the maximum digit.

Radix Sort Java Algorithm

1. Find the length of the number that has maximum number of digits.
2. Initialize i=0, Repeat the below procedure till the length equals i.
3. Fill the bucket with all the digits in ith position.
4. Sort out the digits according to the order.
5. If length=i, i=i*10, goto to step 3. Else go to step 5
6. Print the sorted array.

Complexity

The complexity of Radix Sort is far better than that of bubble sort and some other sorting techniques. It is as shown below depends on d and b.

O (d*(n+b))
d is digits in input integers.
b is the base for representing numbers.

Explanation

Let us start the implementation of the program. First we define a class named RadixSort and obviously it has only one method named sort to sort the numbers given. This function is the central part of discussion and as always, we take the inputs for the user using the main function and pass it on to the sorting function. The below code snippet shows it.

Scanner scan = new Scanner( System.in );

System.out.println("Radix Sort Test\n");
int n, i;

System.out.println("Enter number of integer elements");
n = scan.nextInt();
int arr[] = new int[ n ];

System.out.println("\nEnter "+ \n +" integer elements");
for (i = 0; i < n; i++)
	arr[i] = scan.nextInt();

sort(arr);

You can observe that the function that we are going to implement doesn’t return anything as its return type is void. It takes in an unsorted array of numbers and sorts it. Now we will have a look at the algorithm to implement the sort function. The algorithm says we need to first find the number of digits in the longest number.

for (i = 1; i < n; i++)
            if (a[i] > m)
                m = a[i];

Using the above for loop we can find the maximum of all the numbers. Instead of finding its length we will iterate a while loop until the maximum number falls below zero by dividing the number by 10 for every iteration. Then sort the array using a temporary bucket and array b[ ] and place back the final contents.

while (m / exp > 0)
        {
    int[] bucket = new int[10];
            for (i = 0; i < n; i++)
                bucket[(a[i] / exp) % 10]++;
            for (i = 1; i < 10; i++)
                bucket[i] += bucket[i - 1];
            for (i = n - 1; i >= 0; i--)
                b[--bucket[(a[i] / exp) % 10]] = a[i];
            for (i = 0; i < n; i++)
                a[i] = b[i];
            exp *= 10;        
        }

Radix Sort Java Program

import java.util.Scanner;

class RadixSort 
{
    static void sort( int[] a)
    {
        int i, m = a[0], exp = 1, n = a.length;
        int[] b = new int[10];
        
        for (i = 1; i < n; i++)
            if (a[i] > m)
                m = a[i];
        
        while (m / exp > 0)
        {
            int[] bucket = new int[10];

            for (i = 0; i < n; i++)
                bucket[(a[i] / exp) % 10]++;
            for (i = 1; i < 10; i++)
                bucket[i] += bucket[i - 1];
            for (i = n - 1; i >= 0; i--)
                b[--bucket[(a[i] / exp) % 10]] = a[i];
            for (i = 0; i < n; i++)
                a[i] = b[i];
            exp *= 10;        
        }
    }    
    
    public static void main(String[] args) 
    {
        Scanner scan = new Scanner( System.in );        
        System.out.println("Radix Sort Testn");
        
        int n, i;
        System.out.println("Enter number of integer elements");
        
        n = scan.nextInt();
        int arr[] = new int[ n ];
        
        System.out.println("\nEnter "+ n +" integer elements");
        for (i = 0; i < n; i++)
            arr[i] = scan.nextInt();
        
        sort(arr);
        
        System.out.println("\nElements after sorting ");        
        for (i = 0; i < n; i++)
            System.out.print(arr[i]+" ");            
        
        System.out.println();                     
    }    
}

Output

Radix Sort Test

Enter number of integer elements
6

Enter 6 integer elements
12 9 15 4 0 1

Elements after sorting
0 1 4 9 12 15

Code Reference: https://www.sanfoundry.com/java-program-implement-radix-sort/

Comment below if you have queries or found anything incorrect in above radix sort java program and algorithm.