Radix sort algorithm Java

Sorting algorithms are used to reorder the elements of an array or list in ascending or descending numerical or lexicographic order. Sorting is very important for the optimal performance of other algorithms that require sorted input data.

There are numerous sorting algorithms available. The selection of an appropriate algorithm depends on factors such as the size and characteristics of the input data, available memory, and time and space complexity.

To make your choice easier, in our series we will introduce the most well-known data sorting algorithms, explain their principles, advantages and disadvantages, and program them in Java.

Today we will look at sorting using radix sort.

So far, we have discussed the following:

• Sorting algorithms: Introduction to data sorting
• Bubble sort
• Comb sort
• Big O notation
• Selection sort
• Insertion sort
• Counting sort
• Heap sort
• Merge sort
• Quick sort
• Bucket sort (bin sort)

Radix sort definition

What is radix sort? Radix sort is an efficient sorting algorithm for numbers or strings with fixed-length keys. It belongs to the algorithms that do not work on the principle of comparison, but as the word radix (numerical base) suggests, the sorting is done by successive processing and sorting according to individual digits or characters.

The sorting can start from the end of the string, i.e., from the least significant digit (LSD), or from the beginning, i.e., from the most significant digit (MSD). The sorting uses a modified counting sort algorithm, which we have already introduced. The numbers are always sorted according to one digit position and only then proceed to the next, taking into account the ordering from the previous step.

Although the history of the algorithm dates back to 1887 and in the early 20th century it was used for sorting punched cards, it is still used today in the binary MSD radix sort and is equally used in combination with other algorithms in so-called hybrid algorithms.

Radix sort explained

In our example, we’ll take LSD. This form of radix sort has the advantage over MSD that the sorting algorithm is stable.

Before the actual sorting begins, we need to find out what the maximum number in the unsorted input array is. The number of its digits then determines the number of passes that will be needed to completely sort the input. From our example in the figure, we can see that the maximum number is 958 and the number of passes is 3. Next, we already choose the type of radix sorting (MSD or LSD).

We successively pass digits in place of ones, tens, hundreds, etc. Using counting sort, we find the frequency of each digit, their indices in the sorted result, and then use these to rearrange the numbers in the input to get the sorted numbers based on the current pass. For example. after sorting the numbers in place of the units (blue table), we can notice that the numbers are sorted and at the same time the same numbers still keep their relative order compared to the input (algorithm stability). The green table shows the state after sorting based on tens and the orange table already shows the final sorting result after sorting the hundreds radix. In our example, all numbers were three digits. However, if we had two-digit or single-digit ones among them we would have to treat them as if they had their numeric prefix filled with zeros.

Radix sort animation, visualization, gif

Radix sort advantages

• Fast if the keys are short and from a relatively narrow range
• Also suitable for sorting characters in strings
• The LSD form is always stable, MSD can be adapted to a stable algorithm
• It can be parallelized to spread the computational load across multiple processors

Radix sort disadvantages

• Requires extra memory space
• Not very flexible, it has to be adapted for different data types

Radix sort time complexity

On this page you can go through the steps of the algorithm to check the time taken by the algorithm.

Radix sort implementation, Java code

We will now show an implementation of the Radix sort algorithm (LSD version) in Java.

RadixSort.java

package sorting;

public class RadixSort {
    private final int BASE = 10; // digits [0-9]

    int getMaxElement(int[] data) {
        int max = data[0];
        for (int i = 1; i < data.length; i++)
            if (data[i] > max)
                max = data[i];
        return max;
    }

    public void sort(int[] data)
    {
        // Get maximum element
        int max = getMaxElement(data);
        // Apply counting sort to sort elements based on radix value
        for (int radix = 1; max / radix > 0; radix *= BASE)
            radixCountingSort(data, radix);
    }

    void radixCountingSort(int[] data, int radix) {
        int[] output = new int[data.length + 1];
        int[] count = new int[BASE];
        // Calculate count of elements
        for (int i = 0; i < data.length; i++)
            count[(data[i] / radix) % BASE]++;
        // Calculate cumulative count
        for (int i = 1; i < BASE; i++)
            count[i] += count[i - 1];
        // Place the elements in sorted radix order
        for (int i = data.length - 1; i >= 0; i--) {
            output[count[(data[i] / radix) % BASE] - 1] = data[i];
            count[(data[i] / radix) % BASE]--;
        }
        // Copy array from output back to data
        System.arraycopy(output, 0, data, 0, data.length);
        System.out.print("Radix: " + radix + " -> ");
        printArray(data);
    }

    // Function to print an array
    public void printArray(int[] data)
    {
        for (int i = 0; i < data.length; i++)
            System.out.print(data[i] + " ");
        System.out.println();
    }
}

Main.java

import sorting.RadixSort;

public class Main {
    public static void main(String[] args) {
        int[] dataToSort = { 165, 958, 635, 694, 480, 637, 5, 598, 82};
        RadixSort radixSort = new RadixSort();
        System.out.print("Input: ");
        radixSort.printArray(dataToSort);
        radixSort.sort(dataToSort);
        System.out.print("Sorted: ");
        radixSort.printArray(dataToSort);
    }
}

The output of this radix sort Java code example is:

We have prepared the files with the above example as code that you can run directly in Java. Download the RadixSort Java code here.

About the author

Jozef Wagner

Java Developer Senior

Viac ako 10 rokov programujem v Jave, momentálne pracujem v msg life Slovakia ako Java programátor senior a pomáham zákazníkom implementovať ich požiadavky do poistného softvéru Life Factory. Vo voľnom čase si rád oddýchnem v lese, prípadne si zahrám nejakú dobrú počítačovú hru.