Radix Sort in Java | Radix Sort Program in Java

Problem Description

Write a Java Program to implement Radix Sort Algorithm.

What is Radix Sort in Java?
Radix sort is a sorting algorithm that sorts integers by their digits. It works by grouping numbers by each digit, starting from the least significant digit to the most significant digit. For each digit, the algorithm sorts the numbers into buckets based on the digit value. The buckets are then combined in order to create a sorted list of numbers.

In Java, Radix Sort can be implemented using arrays, queues, or LinkedLists to create the buckets. It has a linear time complexity and is often used to sort large integers, such as in cryptography or big data applications.

Program/Source Code

Here is the source code of the Java program to implement Radix Sort Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

```
/*
```

 * Java Program to Implement Radix Sort

```
 */
```
```
 
```
```
import java.util.Scanner;
```
```
 
```
```
/** Class RadixSort **/
```
```
public class RadixSort 
```
```
{
```
```
    /** Radix Sort function **/
```
```
    public static void sort( int[] a)
```
```
    {
```

        int i, m = a[0], exp = 1, n = a.length;

```
        int[] b = new int[n];
```
```
        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;        
```
```
        }
```
```
    }    
```
```
    /** Main method **/
```

    public static void main(String[] args)

```
    {
```

        Scanner scan = new Scanner( System.in );

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

```
        int n, i;
```

        /** Accept number of elements **/

        System.out.println("Enter number of integer elements");

```
        n = scan.nextInt();
```

        /** Create integer array on n elements **/

```
        int arr[] = new int[ n ];
```
```
        /** Accept elements **/
```

        System.out.println("\nEnter "+ n +" integer elements");

```
        for (i = 0; i < n; i++)
```
```
            arr[i] = scan.nextInt();
```
```
        /** Call method sort **/
```
```
        sort(arr);
```
```
        /** Print sorted Array **/
```

        System.out.println("\nElements after sorting ");

```
        for (i = 0; i < n; i++)
```

            System.out.print(arr[i]+" ");

        System.out.println();

```
    }    
```
```
}
```

Program Explanation

1. The program defines a class called RadixSort that contains a static method called sort, which takes an integer array as input.
2. The sort method begins by finding the maximum element in the input array to determine the number of digits in the largest number. It then initializes an empty array called b with the same length as the input array a.
3. The program then enters a loop that will iterate through each digit of the numbers in the array, starting from the least significant digit to the most significant digit.
4. Within each iteration, the program creates a new array called bucket with a length of 10.
5. The program iterates through the input array and increments the appropriate bucket based on the current digit being examined. It then modifies the bucket array to contain the running sum of elements in each bucket.
6. The program then iterates through the input array in reverse order and places each element into the appropriate position in the output array b based on the current digit being examined. 7. Finally, it copies the sorted elements from array b back into the original input array a.
8. The class also contains a main method that prompts the user to input the number of integers to sort, creates an integer array with that length, prompts the user to input the integers themselves, sorts the array using the sort method, and then prints out the sorted array.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

Time Complexity: O(d * (n + k))
Radix Sort has time complexity O(d * (n + k)), where d is the number of digits in the maximum element, n is the number of elements to be sorted, and k is the range of input values. The implementation finds the max element in O(n) time and uses a bucket array of size 10, taking O(1) time per loop.

Space Complexity: O(n + k)
The space complexity of the implementation is O(n + k), where n is the size of the input array and k is the size of the bucket array. In this case, k is constant and equal to 10, so the space complexity reduces to O(n). Additionally, a new array of size n is created, which also contributes to the space complexity.

Program Output

Radix Sort Test
 
Enter number of integer elements
10
 
Enter 10 integer elements
877 567 3456 876 467 26 934 9876 1 4567
 
Elements after sorting
1 26 467 567 876 877 934 3456 4567 9876

To practice programs on every topic in Java, please visit “Programming Examples in Java”, “Data Structures in Java” and “Algorithms in Java”.

Check this: BCA MCQs | Information Technology MCQs

« Prev - Counting Sort in Java

» Next - Java Program to Implement Brent Cycle Algorithm

Next Steps: