2015-07-07

基数ソート

基数ソートのJava版です。 各桁(十進法)について、分布数え(バケット)ソートを行います。 入力されたn個と同サイズのメモリが確保され、桁ごとにメモリコピーが発生します。 入力データが少ない場合は、とても高速です。

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));
    }
}