Radix sort (Java)

From LiteratePrograms

Other implementations: C | Java

An implementation of radix sort for integers in Java. It uses counting sort for each iteration (see Category:Counting sort for more implementations of counting sort).

<<RadixSort.java>>=
imports
class RadixSort
{
    radix_sort_uint
    main method
}

Contents 1 radix_sort_uint() 1.1 Memory 1.2 The main algorithm 1.3 Counting sort 1.4 Cleanup 2 Test driver

radix_sort_uint()

This function takes an array and the number of bits used as the key in each iteration.

<<radix_sort_uint>>=
public static void radix_sort_uint(int[] a, int bits)
{

Memory

We use an array of the same size as the original array to store the result of each iteration.

<<radix_sort_uint>>=
    int[] b = new int[a.length];
    int[] b_orig = b;

The main algorithm

mask is the bitmask used to extract the sort key. We start with the bits least significant bits and left-shift it the same amount at each iteration. When all the bits are shifted out of the word, we are done.

<<radix_sort_uint>>=
    int rshift = 0;
    for (int mask = ~(-1 << bits); mask != 0; mask <<= bits, rshift += bits) {

Counting sort

An array is needed to store the count for each key value.

<<radix_sort_uint>>=
        int[] cntarray = new int[1 << bits];

We count each key value.

<<radix_sort_uint>>=
        for (int p = 0; p < a.length; ++p) {
            int key = (a[p] & mask) >> rshift;
            ++cntarray[key];
        }

Here, we sum up how many elements there are with lower key values, for each key.

<<radix_sort_uint>>=
		for (int i = 1; i < cntarray.length; ++i)
                    cntarray[i] += cntarray[i-1];

The values in cntarray are used as indexes for storing the values in b. b will then be completely sorted on this iteration's key. Elements with the same key value are stored in their original internal order.

<<radix_sort_uint>>=
        for (int p = a.length-1; p >= 0; --p) {
            int key = (a[p] & mask) >> rshift;
            --cntarray[key];
            b[cntarray[key]] = a[p];
        }

Cleanup

We swap the a and b references, so that the next iteration works on the current b, which is now partially sorted.

<<radix_sort_uint>>=
        int[] temp = b; b = a; a = temp;
    }

If the completely sorted array is in the locally created array, we must copy it to the array provided by the user.

<<radix_sort_uint>>=
    if (a == b_orig)
        System.arraycopy(a, 0, b, 0, a.length);
}

Test driver

This test program uses 4 bits for the key. radix_sort_uint() will accept any number of bits for the key, but it will allocate at least 2^bits ints of storage.

<<imports>>=
import java.util.Arrays;
<<main method>>=
public static void main(String[] args)
{
    int[] a = {
        123,432,654,3123,654,2123,543,131,653,123,
        533,1141,532,213,2241,824,1124,42,134,411,
        491,341,1234,527,388,245,1992,654,243,987};
    System.out.println("Before radix sort:");
    System.out.println(Arrays.toString(a));
    radix_sort_uint(a, 4);
    System.out.println("After radix sort:");
    System.out.println(Arrays.toString(a));
}

Download code