Radix sort algorithm Java

Selection sort 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 a number of different sorting algorithms. 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 requirements.

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:

• Sorting algorithms: an introduction to data sorting,
• Bubble sort,
• Comb sort,
• Big O notation: analyzing the complexity of algorithms,
• Selection sort – sorting by selection,
• Insertion sort – sorting by insertion,
• Counting sort – sorting by counting,
• Heap sort,
• Merge sort – sorting by splitting and merging,
• Quick sort – fast sorting with pivot,
• Bucket sort (bin sort) – sorting using buckets (bins).

What is radix sort algorithm? – definition

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 (i.e. numerical order) 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 countingsort algorithm, which we have already introduced. The numbers are always sorted according to one order 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 labels, 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 principle 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 field 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 transitions 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 sorts, we find the multiplicity 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 transition.

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 retain their relative order compared to the input (stability of the algorithm). 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 algorithm advantages

• Fast if the keys are short and from a relatively narrow band.
• Also suitable for sorting characters in strings (string).
• 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 algorithm disadvantages

• Requires extra memory space.
• It is 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 consumption of 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 example is:

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

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.