バケットソート(ビンソート) | アルゴリズム [AOJ 10029][Java]

今回は、『AOJ 10029 - ソートアルゴリズム』をバケットソート(ビンソート、度数ソート)で解いてみました。

JavaのArray系のデータ構造をあまりわかっていないまま使っています。おそらくもう少し効率的なデータ構造を使って表現すれば処理やメモリ使用量が効率化すると思います。

🚜 概要

bucket-sort-algorithm

ハッシュと挿入ソートを組み合わせたソートである

🎃 計算量

与えられたハッシュ関数にもとづいて、対応するバケットに値を挿入する => o(n)
バケットに複数の要素があれば、挿入ソートを行う => 期待値はo(n)
バケットの数が少なすぎると挿入ソートの計算量に近付きo(nの2乗) となる

🤔 AOJ問題

AOJ 10029 - ソートアルゴリズム

🎉 Javaコード

import java.io.BufferedReader;
import java.io.InputStreamReader;

class Main {
    public static void main(String[] a) throws Exception {
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(r.readLine());
        String[] str = r.readLine().split(" ");

        int[] arr = strToIntArray(str);
        int maxValue = maxValue(arr);

        int[] bucket = new int[maxValue + 1];
        for (int i = 0; i < n; i++) {
            bucket[arr[i]] += 1;
        }

        int index = 0;
        for (int i = 0; i < bucket.length; i++) {
            while (bucket[i] > 0) {
                arr[index] = i;
                bucket[i] --;
                index ++;
            }
        }

        StringBuilder s = new StringBuilder();
        for (int i = 0; i < n; i++) {
            s.append(arr[i]);
            if (i != n - 1) {
                s.append(" ");
            }
        }

        System.out.println(s);
    }

    private static int[] strToIntArray(String[] str) {
        int[] arr = new int[str.length];
        for (int i = 0; i < str.length; i++) {
            arr[i] = Integer.parseInt(str[i]);
        }
        return arr;
    }

    private static int maxValue(int[] arr) {
        int max = -1;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        return max;
    }
}