バケットソート

バケットソートとは、別名バケツソートとも呼ばれ、あらかじめ順番通り並べて準備されたバケツに、データを放り込むことで並べ替えを行おうという、いささか乱暴なソートアルゴリズムです。

この方法は、データの存在する範囲が有限個に限定されていないと使えませんが、使える場合は非常に高速に並べ替えを実行できる、きわめて有用なアルゴリズムです。

考え方

1〜100までの数字が書かれたたくさんのカードがあるとします。カードに書かれている数字には重複があっても構いません。また、最初、カードはばらばらに混ざっています。

これらのカードを、数字が小さい順に並べ替えるのに、バケットソートでは、1〜100までの数字が横に書かれている100個のバケツを準備します。

そして、カードを適当に取り出して、その番号と一致するバケツに放り込みます。また、別なカードを取り出しては、対応するバケツに放り込みます。

これをカードがなくなるまで繰り返したら、次に、1番のバケツから順番にカードを取りだし、次々と下に重ねていきます。1番のバケツが空になったら、次は2番のバケツから取り出します。その次は3番のバケツから…、という具合に、全部のバケツから順番にカードを取り出して、下に重ねます。

これで、見事にカードは小さい順に並んでいる、というわけです。

bucket-sort-image.gif (11632 バイト)

アルゴリズム

バケットソートを行うには、バケツを何個準備すれば良いかが大変重要です。それはつまり、データが取りうる値の範囲が有限で、既知でなければならないと言うことを意味します。

ここでは、データの範囲は 0〜m-1 までの整数値として、m個のバケツを準備して、話を進めます。

以下に、Java で書いたバケットソートのプログラムを示します。

  public void sort(int[] a){

    // m 個分のバケツを用意します
    DList[]  bucket=new DList[m];
    for(int i=0;i<bucket.length;i++)
      bucket[i]=new DList();

    // まず、すべてのデータを対応するバケツに放り込みます。
    for(int i=0;i<a.length;i++)
      bucket[a[i]+min].add(new Integer(a[i]));

    // バケツの順番に中のデータを取りだし、配列に格納します。
    for(int i=0,j=0;i<bucket.length;i++){
      while(bucket[i].num>0){
	Integer ai=(Integer)bucket[i].removeFirst();
	a[j]=ai.intValue();
      }
    }
  }
【アルゴリズム2】 バケットソート

このプログラムでは、バケツとして双方向リストクラス DList の配列を使用しています。双方向リストクラスは Java に標準では備わっていませんから、自作しています。これについて詳しくはクラスの DList と DLink を参照してください。

ここでは、i 番目のバケツ bucket[i] について、次の知識があれば十分です。

bucket[i].add(d) バケツにデータを入れます。バケツには複数のデータを次々に入れることができます。
bucket[i].num 現在、バケツに入っているデータの数を意味します。
bucket[i].removeFirst() バケツに最初に入れられたデータを取り出します。そのデータは、バケツの中からなくなります。

バケットソートアルゴリズムでは、まず、すべてのデータを対応するバケツに放り込みます。この処理は、for ループで並べ替えたい配列のすべての要素をまわして、その要素の数値に対応するバケツ(Vector)に addElement() しています。このとき、Integer クラスを生成している理由は、DList クラスは Object クラスから派生したオブジェクトでなければ格納できないからです。int 型はクラスのオブジェクトではないので、そのままでは DList に入れることができません。

すべてのデータをバケツに入れ終わったら、次にそれらを1つずつ取りだし、元の配列 a[ ] に入れなおしていきます。これには2重ループが使われています。外側のループでバケツを順番にまわして、内側のループでそのバケツの中のデータを順番に取り出しています。配列 a[ ] のインデックスには、データを a[ ] に格納する毎にカウントアップする変数 j を使用しています。これによって、取り出されたデータは順番に配列 a[ ] に格納されていきます。

以上により、この2重ループを終了した時点で、a[ ] にはもとのデータが小さい順に整列されたデータが格納されていることになります。

バケットソートの動作

バケットソートを可視化して行うアプレットを、下に示します。

"Start" ボタンを押すと、並べ替えが2パスで行われます。まず最初に、青い線が上から順番に移動します。これは、青い線のデータをバケツに放り込んでいることを意味しています。このとき、同時に画面の右側にバケツに入っているデータの数がで表示されます。このバケツは、上から順に1番目、2番目…と並んでいます。

次に、赤い線が上から下に移動し、それとともにデータが小さい番号のバケツから順番に取り出されて、小さい順に並べ替わります。これは、バケツからデータを順番に取り出して、配列 a[ ] に入れていることを意味しています。全部のバケツからデータを取り出し終わったら、並べ替えは終了です。

並べ替えの過程を注意深く観察すると、バケツに入れるときはばらばらにバケツに入りますが、取り出すときは上から順番になくなることがわかります。

データの生成方法を "Radix10" にすると、データが10進数3桁の乱数になります。この場合、1000個のバケツが準備されますので、バケツの表示が非常に小さくなり、かつ、画面に入りきらずに下に見えないバケツが出てきてしまいます。この問題は、次章の基数ソートで対応します。

計算時間の評価

バケットソートの処理は、データをバケツに放り込む処理と、バケツからデータを取り出す処理の2つの組み合わせです。データ数を N とすると、これらの処理はそれぞれ O(N) の時間を要しますから、全体で O(2N) ですから、O(N) となります。

テキストでは、連結のオーダーは O(m+n) と書いてありますが、これは、配列を実際に結合 (CONCATENATE) しているからです。今の例のように、もとの配列にリストから取り出すようにすれば、要する処理オーダーは O(2N) となります。

したがって、バケットソートはたかだか要素数に比例した時間で並べ替えを行うことができる、大変優れたソートアルゴリズムであることになります。

しかし、このアルゴリズムは、2つの点で制限や問題があります。

  1. バケツを用意するためには、データの値の範囲が有限個の整数で表現できなければならない。
  2. データの値の種類の分だけバケツを準備しなければならないので、メモリを浪費してしまう可能性がある。

特に2番目は、本質的な問題を含んでいます。

100点満点のテストの点数で並べ替えるような場合は、せいぜい101個の(0点の人の分も)バケツを準備すれば済みます。

しかし、銀行の個人口座の預金残高で並べ替えを行いたい場合は、いったい何個のバケツを準備すれば良いでしょうか。銀行に個人で一兆円も貯金している人はいないでしょうから、0円から1,000,000,000,000円までの間の整数を格納できる必要があります。つまり、1,000,000,000,001個のバケツが必要になるわけです。バケツ1個が仮に8バイトのデータを消費するとすると、いかに最近のパソコンのメモリが増えてきたらかといって、8T(テラ)バイトのメモリはとても準備できませんね。しかも、そのほとんどのバケツは、空のまま、使われないはずです。

このような問題を解決するために、バケットソートの変形である基数ソートが考案されました。次章では、この基数ソートについて見てみましょう。

← prev | next →