【Java】アルゴリズムの基本：バケットソートを実装してみ

データの並べ替え（ソート）には様々な方法がありますが、今回は「バケット（バケツ）」に見立てた配列を使って整理する「バケットソート」をJavaで実装してみます。

1. バケットソートの仕組み

例えば (3, 6, 1) というデータを昇順に並べ替える場合、以下のような手順を踏みます。

1. 最大値を見つける：今回の例では「6」です。

2. バケツ（配列）を用意する：最大値と同じサイズ、または 最大値 + 1 の配列 a[ ] を用意します。

3. 初期化：配列の全要素を「0」などで初期化します。

4. データをバケツに入れる：元のデータの値をそのまま「添え字（インデックス）」として使い、値を格納します。

   • 3 は a[3] へ

   • 6 は a[6] へ

   • 1 は a[1] へ

5. 取り出す：バケツの配列を先頭から確認し、初期値以外のものを取り出せば整列が完了します。

---

2. Javaでの実装例

Java

public class BucketSort {
    public static void main(String[] args) {
        int[] data = {3, 6, 1};
        
        // 1. 最大値を見つける
        int max = 0;
        for (int i : data) {
            if (i > max) max = i;
        }

        // 2 & 3. 最大値分の配列（バケツ）を用意し初期化
        // ※ 0〜maxまで必要なのでサイズは max + 1
        int[] buckets = new int[max + 1];

        // 4 & 5 & 6. データを対応する添え字のバケツに入れる
        for (int value : data) {
            buckets[value] = value;
        }

        // 7. 初期値（0）でないものを順に取り出す
        System.out.print("ソート結果: ");
        for (int i = 0; i < buckets.length; i++) {
            if (buckets[i] != 0) {
                System.out.print(buckets[i] + " ");
            }
        }
        
        /* * 実行結果 (System.out.println 出力例)
         * ソート結果: 1 3 6 
         */
    }
}

---

3. バケットソートの注意点

このアルゴリズムは非常に高速ですが、いくつか実用上の注意点があります。

• メモリ使用量：最大値が「100万」であれば、たとえデータが3つしかなくても、100万要素の巨大な配列を確保する必要があります。

• データの種類：添え字として値を使うため、基本的には「0以上の整数」に向いています。

• 重複データ：今回の簡易的な実装では、同じ値が複数あると上書きされてしまいます（重複に対応する場合は、バケツの中身をカウント形式にするなどの修正が必要です）。

アルゴリズムの学習として、まずはこの「値と添え字を対応させる」という考え方に触れてみるのがおすすめです。