2015-07-07

Radix Sort

Java version of Radix Sort. Counting(bucket) sort by each digit. (decimal number). Same size (n) memory allocated as input size and memory copy each digit. It is very fast if the input data size is small.

package com.clustack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class RadixSort {

    public static Integer[] sort(Integer[] arr, boolean desc) {
        int n = arr.length;

        int i;
        Integer maxValue = null;
        int exp = 1; // digit
        Integer[] tmp = new Integer[n];
        Integer[] hists = new Integer[10];

        while (true) {
            Arrays.fill(hists, 0);

            if (maxValue == null) { // for exit condition
                maxValue = arr[0];
                for (int ar : arr) {
                    if (ar > maxValue)
                        maxValue = ar;
                    hists[(ar / exp) % 10]++; // frequency distribution of digit 0..9
                }
            } else {
                for (int ar : arr)
                    hists[(ar / exp) % 10]++; // frequency distribution of digit 0..9
            }

            if (desc) {
                for (i = 9; i > 0; i--)
                    hists[i - 1] += hists[i]; // cumulative frequency distribution
            } else { // ascending order
                for (i = 1; i < 10; i++)
                    hists[i] += hists[i - 1]; // cumulative frequency distribution
            }
            for (i = n - 1; i >= 0; i--)
                tmp[--hists[(arr[i] / exp) % 10]] = arr[i];

            exp *= 10; // next digit
            if (maxValue / exp <= 0)
                return tmp;
            System.arraycopy(tmp, 0, arr, 0, n); // copy to results array
        }
    }

    public static void main(String[] args) {
        List<Integer> lists = new ArrayList<>();
        for (int i = 0; i < 100; i++)
            lists.add(i);
        Collections.shuffle(lists);
        System.out.println("Unsorted:" + lists);
        Integer[] results = RadixSort.sort(lists.toArray(new Integer[0]), false);
        System.out.println("Sorted(asc): " + Arrays.asList(results));

        System.out.println("\nUnsorted:" + lists);
        results = RadixSort.sort(lists.toArray(new Integer[0]), true);
        System.out.println("Sorted(desc): " + Arrays.asList(results));
    }
}