Implement Radix Sort Using Java

If you’re in a computer science background, widening your technical horizons is the best thing you should do. However, your programming skills matter the most. And one must continuously keep sharpening these skills, to become a better programmer in the future. Though there are multiple things to focus on, one specific area you must focus on is the world of data structures. Data structures in general are particular approaches to solve problems so that computer resources get used minimum. In general, there are multiple data structures you can learn and implement as well. However, we’ve covered some basic data structures before, so, now we’ll move towards some advanced data structures. Hence, today we’re going to learn how to Implement Radix Sort using Java.

 

What is Radix Sort?

 

• Unlike simpler data structures, Radix Sort uses a different sorting approach to arrange elements in sequential order.

 

• Here, elements (be it Integers or Strings) are sorted based on the position of digits i.e, from least significant to most significant.

 

• No of iterations in this sorting method may vary significantly. As iterations are directly proportional to the no of digits present in the largest element in a list/array.

 

Also Read: Implement Bubble Sort using Java

 

What’s The Approach?

 

• To make this program look cleaner and easier, we’ll divide it into three major sections.

 

• In the first part, we’ll find the largest number in an array using getMax().

 

• As for the second part, we’ll pass the exponential exp value to the counting sort function.

 

• At the final stage, we’ll apply counting sort to sort the array in ascending order w.r.t the exponential value being passed.

 

• In Counting Sort, we are going to sort array elements based on single digits only. Starting from one’s place and incrementing the exponential by 10 for each iteration. This condition is going to be executed till m/exp > 0   remains true (m holds the value of the largest integer in an array).

 

Java Program To Implement Radix Sort

 

Input:

170, 45, 75, 90, 802, 24, 2, 66

 

Output:

2 24 45 66 75 90 170 802

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

class TechDecodeTuorials{

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

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

        // Store count of occurrences in count[]
        for (i = 0; i < n; i++)
            count[(arr[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 = n - 1; i >= 0; i--) {
            output[count[(arr[i] / exp) % 10] - 1] = arr[i];
            count[(arr[i] / exp) % 10]--;
        }

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

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

        // Do counting sort for every digit.exp is passed.
        // exp is 10^i where i is current digit number
        for (int exp = 1; m / exp > 0; exp *= 10)
            countSort(arr, n, exp);
    }

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

    /*Driver Code*/
    public static void main(String[] args)
    {
        int arr[] = { 170, 45, 75, 90, 802, 24, 2, 66 };
        int n = arr.length;
        
        // Function Call
        radixsort(arr, n);
        print(arr, n);
    }
}