基数ソート

基数ソートは、前章で見たバケットソートの変形です。

このソートアルゴリズムは、各要素が 0 以上、mk-1 以下の整数値、つまり k 桁の m 進数であるときに、各桁毎に合計 k 回のバケットソートを適用すると、すべての要素を並べ替えることができる、ということに着目しています。

考え方

基数ソートの考え方を示すために、具体的な例をあげてみましょう。

分かりやすいように10進数3桁の数字が20個あるとします。

未整列データ
123 973 206 215 77
527 426 885 300 681
732 994 258 770 359
512 863 44 137 905

10進数の数字ですから、10個のバケツを準備して、0〜9までの番号をつけておきます。

まず最初に、データの下位1桁目を見て、対応するバケツに放り込みます。次に、上のバケツに入っているデータから順に、2桁目を見て、対応するバケツに放り込みます。最後に同様に3桁目を見て、対応するバケツに放り込みます。

1回目 2回目 3回目
バケツ データ
0 300,770
1 681
2 732,512
3 123,973,863
4 994,44
5 215,885,905
6 206,426
7 77,527,137
8 258
9 359
→
バケツ データ
0 300,905,206
1 512,215
2 123,426,527
3 732,137
4 44
5 258,359
6 863
7 770,973,77
8 681,885
9 994
→
バケツ データ
0 44,77
1 123,137
2 206,215,258
3 300,359
4 426
5 512,527
6 681
7 732,770
8 863,885
9 905,973,994

最終的に出来上がったバケツのデータを上から見ると、小さい順に並んでいることがわかります。

アルゴリズム

Java で書いた基数ソートのアルゴリズムを以下に示します。数字を m 進数で考える場合、バケツの個数は m になります。

  public void sort(int[] a){

    // バケツに入っているデータ数を覚えるための配列です
    int[] bn=new int[bucket.length];

    // 最下位桁の数字を見て、対応するバケツにデータを入れます。
    for(int i=0;i<a.length;i++){
      bucket[a[i]%m].add(new Integer(a[i]));
      notifier.notify(i,-1);
    }

    // 最初のバケツから順番にデータを取りだし、データの指定桁の値を見て、
    // 対応するバケツにデータを追加します。
    for(int j=1;j<k;j++){

      // 現在、それぞれのバケツに何個のデータが入っているかを
      // 覚えておきます。
      for(int b=0;b<bucket.length;b++)
	bn[b]=bucket[b].num;

      // 各バケツの先頭から bn[b] 個のデータについて、
      // j 桁目の値によって対応するバケツに入れ替えます。
      // バケツの末尾に追加するので、前のデータと混ざることはありません。
      for(int b=0,c=0;b<bucket.length;b++){
	for(int i=0;i<bn[b];i++){
	  Integer ai=(Integer)bucket[b].removeFirst();
	  bucket[(int)(ai.intValue()/(Math.pow(m,j)))%m].add(ai);
	  notifier.notify(c++,-1);
	}
      }
    }

    // バケツの順番に中のデータを取りだし、配列に格納します。
    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();
	notifier.notify(-1,j++);
      }
    }
  }
【アルゴリズム3】 基数ソート

バケツとしては、前章のバケットソートと同じ双方向リスト DList を使用しています。

2回目以降のデータの入れ替え部分（リストの青い部分）は、下の図のような方法で m 個以上のバケツを使うことなく、並べ替えを実現しています。

radix-sort-image.gif (5375 バイト)

まず最初に、各バケツに何個のデータが入っているかを覚えておきます。これは、バケツに後から追加されたデータが、前からあるデータと混ざってしまわないために必要です。

そして、先頭のバケツから順番にデータを1つずつ取りだし、次の桁が対応するバケツの末尾に追加します。

これを、青いデータがなくなるまで行えば、次の桁によって並び替わったバケツが得られます。さらに次の桁も処理する必要があれば、同様なことを繰り返せば OK です。

最後に、バケツのデータを配列 a[ ] に格納して、並べ替えは完了です。

基数ソートの動作

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

基数ソートの場合、データの発生方法を "Radix10" にしたほうが、よくわかります。"Uniform" や "Overlap" では、発生するデータの値が小さすぎて、ほとんどのデータが1桁か2桁になってしまうため、最終的に最初のバケツにデータが集中してしまいます。

"Radix10" で実行した場合、前章のバケットソートではバケツが多すぎて下にはみ出していたものが、基数ソートでは（10進数なので）常に10個のバケツで処理できていることがわかります。

反面、バケットソートでは2回の処理で並べ替えが完了していたものが、基数ソートでは4回処理を行わないと、並べ替えが完了しないこともわかります。これは、バケツの数を少なくした代わりに、各桁毎にバケツの入れ替えをしなければならなくなったことが原因です。

計算時間の評価

基数ソートは基本的にはバケットソートの繰り返しですから、オーダーもバケットソートの定数倍になります。

具体的には、m 進数 k 桁までの N 個のデータを並べ替える場合、バケツの入れ替えが k 回必要ですから、それだけで O(kN) になります。さらに、最後に配列 a[ ] に格納するのに O(N) 必要ですから、合計 O(kN+N) となりますが、オーダーとしては O(kN) です。

基数ソートは、バケットソートに比べて広い範囲のデータを取り扱うことができますが、反面、実行速度はほぼ 1/k 倍に落ちます。それでも、1,000,000,000,000個のバケツを準備することを考えれば、（1,000,000,000,000 = 1012 なので）10個のバケツでスピードが1/12に落ちても、まだ現実的であると思えます。あるいは、1006 と考えて、100個のバケツでスピードが1/6、とすることもできるでしょう。

← prev | next →