バケットソート
出典: フリー百科事典『ウィキペディア（Wikipedia）』
バケットソートは、ソートのアルゴリズムの一つ。バケツソート、分布数えソート、ビンソートなどともいう。計算時間はO(n)と高速だが、O(n)の外部記憶が必要。安定ソートが可能。
目次 |
[編集] 概念
整列したいデータの取りうる値がm種類であるとき、m個のバケツを用意しておき、値ごとに1個のバケツを対応づける。元のデータ列を走査して、各データを対応するバケツに入れていく。この処理が終わった後、整列したい順序に従ってバケツから値を取り出せば、データをソートすることができる。
安定ソートを実現するためには、同じバケツに入っているデータは入れたときと同じ順序で取り出す必要がある。順序が保存されない場合は、ソートはできるが、安定ソートではなくなる。後述するように基数ソートと組み合わせて使うためには、安定ソートになっている必要がある。
[編集] 実装
バケットソートには、大きく分けて2種類の実装がある。
まずひとつは、可変個の要素を保持できるデータ構造を使ってバケツを表現する方法である。簡単な例としては、m個の線形リストを使う実装が考えられる。直感的に理解しやすい実装だが、単純な配列だけではなく可変長のデータ構造が必要になるため、その実装コストを考慮しておく必要がある。
もうひとつは、いったん整列対象のデータを走査して値ごとの出現回数を数えておき、それに応じてひとつの配列の中を値ごとに分割する方法である。例えば以下の入力が与えられたとする。
3 2 2 1 2 2 1 3 3 1 2 3
昇順にソートした結果は以下のようになるはずである。
1 1 1 2 2 2 2 2 3 3 3 3
さて値ごとの出現個数を調べると、1が3個、2が5個、3が4個出現していることがわかる（ソートしなくても元のデータ列に一通りアクセスすればわかる）。出現個数がわかれば、1は結果列の1番から、2は4番から、3は9番から始まることがわかる。
[編集] 利点と欠点
多くのソートアルゴリズムの計算量がO(nlogn)である中、O(n)を実現でき、多数のデータを高速に処理できることが利点である。
欠点は、取りうる値の種類mに対応するバケツが必要な点である。仮にキーが32ビット整数という以外に事前情報がないデータ列をソートする場合、約43億個のバケツが必要にある。長さに制限のない可変長の文字列の場合は、もはや有限個のバケツでは対応できない。この欠点は、基数ソートと組み合わせることで回避できる場合もある。
