バケットソート(ビンソート [Bin Sort] とも呼ばれる)はあらかじめデータがとりうる値すべての容器(バケット)を順番どおりに並べて用意しておき、値を対応する容器に移すことでソートを行う整列アルゴリズムです。

データがとりうる値がわかっていなければソートのためのバケット [Bucket] を準備することができないのでこのアルゴリズムは使えません。比較を用いない整列アルゴリズムです。

アルゴリズム分析

前提としてソート対象のデータは 1 から 10 の整数とします。

1. 1 から 10 に対応する10個のバケットを順に並べて用意する
2. データを対応するバケットに入れる
3. バケットから順にデータを取り出す

このような方法で整列されたデータを得ることができます。

ソート対象のデータは必ず10個存在するとは限りません。1 から 5 までの5個しかデータがなくてもバケットは10個用意する必要があります。6 から 10 のバケットはデータを取り出す際に無視することで 1 から 5 のデータだけを整列させるのです。

図解

特徴

冒頭で述べたようにソート対象のデータがとりうる値をあらかじめわかっていなければバケットの用意ができないので、このアルゴリズムは使えません。また、バケットという作業領域が必要になるのでデータの範囲が大きすぎるとバケットのための領域(メモリ)を確保できません。データの範囲が1から1024として、バケット1つに 1byte の領域が必要になるのならバケットを用意するだけで 1kb の領域が必要になります。データの範囲が100,000、1,000,000 と大きくなることを想像すれば大きな範囲のデータが扱えないことは理解できるでしょう。

もうひとつ、ソート対象のデータは重複が許されないということです。バケットは想定される値をキーとして用意されます。ですから同値が存在しても対応する複数のバケットを用意できないのです。ただし、この問題を解決した別のアルゴリズムに分布数え上げソートというものがあります。

サンプルコード

C言語

配列を昇順に整列させます。

#define M 10 /* データ範囲の最大値 */

/**
 * numbers[] ソート対象の配列
 * number_of_item ソートの対象となるデータの個数。numbers中のソートさせたいデータの数。
 */
void bucket_sort(int numbers[], int number_of_item)
{
    int buckets[M];
    int i; /* ループカウント変数 */

    /* prepare buckets バケットを用意 */
    for (i = 0; i < M; i++) {
        buckets[i] = 0;
    }
    /* putting in bucket 元のデータをバケットに入れる*/
    for (i = 0; i < number_of_item; i++) {
        buckets[numbers[i]] = numbers[i];
    }
    /* back into the original array バケットから元の配列に戻す*/
    int j = 0; /* 配列のインデックス */
    for (i = 0; i < M; i++) {
        if (0 < buckets[i]) {
            numbers[j++] = buckets[i];
        }
    }
}

バケットソートのデモンストレーション プログラム: bucket_sort.c

Python

MIN_BUCKET = 0
MAX_BUCKET = 15

def bucket_sort(aList):
    buckets = list()
    for i in range(MIN_BUCKET, MAX_BUCKET + 1):
        buckets.append(None)

    for i in aList:
        buckets[aList[i]] = aList[i]

    x = 0
    for i in range(MIN_BUCKET, MAX_BUCKET + 1):
        if buckets[i] is not None:
            aList[x] = buckets[i]
            x += 1

    return aList


if __name__ == '__main__':
    from random import shuffle
    l = range(15)
    lcopy = l[:]
    shuffle(l)
    print('Unsorted')
    print l
    assert l != lcopy
    print ('Sorted')
    l = bucket_sort(l)
    print l
    assert l == lcopy

• ヒープソート
• 分布数え上げソート

---