バケットソート

バケットソートとは

バケットソート(ビンソート)とは、その使用に強い制限を前提とするが、計算量が O(n) という非常に高速なソートアルゴリズムです。バブルソートやクイックソートとは違い、非比較ソートアルゴリズムの為、比較ソートの下限である計算量 O(n log n) より高速に動作する可能性を持っています。

使用にはソート対象のデータについて、「ソート対象のデータ(キー)の取りうる値が m種類であること」という前提を必要とします。

事前にデータの取りうる値が m種類とわかっているので、それに対応した入れ物(バケツ)を昇順ないし降順で用意し、そこに全データを入れてしまい、それから順に取り出していけば、ソート結果のデータが得られるというアルゴリズムです。当然 m が大きいほど、用意しなければならないバケツのサイズが増えるので、メモリ使用量が増えていきます。そういう意味でもほかの比較ソートアルゴリズムとは異なります。

バケットソートは、安定な外部ソートです。計算量が O(n) で高速ですが、n個のデータが入るバケットm個を用意する必要があるため、メモリ使用量 O(nm) となります。これは、32bit整数値を対象にソートする場合、m=約43億という膨大なバケットが必要となることを意味します。これでは使い物にならないので実際には、m が十分に小さいことも前提条件として必要になります。

バケットソートのシミュレーション

バケットソートのメリットは計算量が O(n) であること以外にも、データの比較を行わなくてもよいという点があります。シミュレータの動きをみると、比較なしで次々に対応のバケツに値が放り込まれているのがわかります。すべてを入れ終わると後はつなげるだけです。

アルゴリズムの解説

整数値0～9までの値をとりうる5件のデータについて、バケットソートを適用させる例を考えます。

長さ5の配列を10個用意します。この配列がバケツです。
データを取出し、対応するバケツに入れる作業を全データに対して行います。
バケツの中身のデータをすべて順に取出します。

以下のサンプルコード(C#)では、連結リスト(List)を使って動的に長さを確保する方法を採っています。

サンプルコード

C#

// 整数値(0～max)のバケットソート
public static void BucketSort(int[] array, int max)
{
    // 整数値のソートなので、数値を入れるのではなく
    // データの個数をカウントする用のバケツを用意
    int[] bucket = new int[max + 1];

    // バケツに値を入れます
    for (int i = 0; i < array.Length; i++)
    {
        // 対象のバケツの個数をカウントアップ
        bucket[array[i]]++;
    }

    // バケツ中の値を結合します
    for (int j = 0, i = 0; j < bucket.Length; j++)
    {
        for (int k = bucket[j]; k != 0; k--, i++)
        {
            array[i] = j;
        }
    }
}

// 整数値をキー(0～max)とする任意の型に対するバケットソート
public static void BucketSort<T>(T[] array, Func<T, int> getKey, int max)
{
    // バケット作成
    var buckets = new List<T>[max + 1];

    // バケットに値を入れる
    foreach (var item in array)
    {
        // ソート対象データのキー(整数値)を取得
        int key = getKey(item);
        if (buckets[key] == null) buckets[key] = new List<T>();
        buckets[key].Add(item);
    }

    // バケット内の値を結合
    int i = 0;
    foreach (var bucket in buckets)
    {
        if (bucket != null)
        {
            foreach (T val in bucket)
            {
                array[i++] = val;
            }
        }
    }
}

Python

# バケットソート(分布数え上げソート)
def couonting_sort(array, max):
    # バケットを作成し、値を入れていく
    bucket = [0] * (max+1)

    # 値を入れる(数える)
    for val in array:
        bucket[val] += 1

    # バケツの中身を取り出して結合
    i = 0
    for n in range(len(bucket)):
        for j in range(bucket[n]):
            array[i] = n
            i += 1

# バケットソート
def bucket_sort(array, get_key, max):
    # バケットを作成
    bucket = [None] * (max+1)

    # バケットにデータを追加していく
    for p in array:
        key = get_key(p)
        if bucket[key] is None: bucket[key] = list()
        bucket[key].append(p)

    # バケットの中身を結合
    i = 0
    for n in range(len(bucket)):
        if bucket[n] is None: continue
        for p in bucket[n]:
            array[i] = p
            i += 1

ヒープソート基数ソート

TOP

アルゴリズム初心者向けの基礎と入門(C#, Pythonとか)