バケットソート(ビンソート) | アルゴリズム [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;
    }
}

🍮 参考リンク

🖥 VULTRおすすめ

「VULTR」はVPSサーバのサービスです。日本にリージョンがあり、最安は512MBで2.5ドル/月($0.004/時間)で借りることができます。4GBメモリでも月20ドルです。最近はVULTRのヘビーユーザーになので、「ここ」から会員登録してもらえるとサービス開発が捗ります！

酒と泪とRubyとRailsと