「整列 (sorting) 」の続きです。今回はヒープソート、マージソート、分布数えソート、基数ソート (直接基数法、基数交換法) について説明します。
ヒープ (heap) は 二分木とヒープ で説明したデータ構造です。実は、このヒープを使ったソートも優秀なアルゴリズムの一つです。実行時間は n * log n に比例しますが、平均するとクイックソートよりも遅くなります。しかし、クイックソートとは違って、データの種類によって性能が劣化することはありません。
プログラムは次のようになります。
リスト : ヒープソート
def heap_sort(buff):
# ヒープの構成
size = len(buff)
for i in xrange(size / 2 - 1, -1, -1):
n = i
x = buff[n]
while True:
c = 2 * n + 1
if c >= size: break
if c + 1 < size and buff[c] < buff[c + 1]: c += 1
if x >= buff[c]: break
buff[n] = buff[c]
n = c
buff[n] = x
# 最大値を取り出す
for i in xrange(size - 1, -1, -1):
x = buff[i]
buff[i] = buff[0]
n = 0
while True:
c = 2 * n + 1
if c >= i: break
if c + 1 < i and buff[c] < buff[c + 1]: c += 1
if x >= buff[c]: break
buff[n] = buff[c]
n = c
buff[n] = x
前半部分でヒープを構築します。親子関係が 二分木とヒープ の説明と逆になっていることに注意してください。つまり、親が子より大きいという関係を満たすようにヒープを構築します。したがって、配列の先頭 (buff[0]) が最大値になります。
後半部分で、最大値を取り出してヒープを再構築します。配列の先頭には最大値がセットされているので、これを配列の最後尾のデータと交換します。あとは、そのデータを除いた範囲でヒープを再構築すれば、その次に大きいデータを求めることができます。これを繰り返すことで、大きいデータが配列の後ろから整列していくことになります。
最初の for ループで、配列の前半部分のデータを後ろから順番に取り出します。次の while ループで、親子関係を満たすように修正します。変数 n が親の位置を、変数 c が子の位置を示します。次に、後半の for ループで、最大値 buff[0] と最後尾のデータ buff[i] を交換します。そして、while ループでヒープの再構築を行います。あとはヒープのプログラムとほとんど同じですが、ヒープを再構築する範囲が変数 i で管理されていて、その値は一つずつ減っていくことに注意してください。
それでは実行結果を示します。
表 : heap sort の結果 (単位 : 秒) 個数 乱数 昇順 逆順 山型 ----------------------------------- 1000 : 0.012 0.012 0.011 0.012 2000 : 0.026 0.027 0.025 0.027 4000 : 0.058 0.060 0.054 0.058 8000 : 0.125 0.131 0.118 0.127 16000 : 0.271 0.282 0.257 0.273 32000 : 0.584 0.603 0.556 0.587 実行環境 : Windows XP, celeron 1.40 GHz, Python 2.4.2
このように、ヒープソートはどのデータに対しても、そこそこの速度でソートすることができます。ただし、実行時間はクイックソートよりも遅くなりました。参考文献 [3] によると、ヒープソートの速度はクイックソートの半分くらいといわれています。ヒープソートの処理内容はクイックソートよりも複雑なので、時間がかかるのは仕方がないところでしょう。
マージ（併合 : merge）とはソート済みの複数の列を一つの列にまとめる操作のことです。このマージを使ったソートを「マージソート (merge sort) 」といいます。最初にマージについて簡単に説明します。次の図を見てください。
┌─ (1, 3, 5) ; リスト a
() ←┤
└─ (2, 4, 6) ; リスト b
小さい方をセットする
┌─ (3, 5) ; リスト a
(1) ←┘
(2, 4, 6) ; リスト b
1 をセットする
(3, 5) ; リスト a
(1, 2) ←┐
└─ (4, 6) ; リスト b
2 をセットする
データがなくなるまで繰り返す
図 : マージの考え方
2 つのリスト a と b があります。これらのリストはソート済みとしましょう。これらのリストをソート済みのリストにまとめることを考えます。 a と b はソート済みなので先頭のデータがいちばん小さな値です。したがって、上図のように先頭のデータを比較し、小さい方のデータを取り出して順番に並べていけば、ソート済みのリストにまとめることができます。途中でどちらかのリストが空になったら、残ったリストのデータをそのまま追加します。当たり前だと思われるでしょうが、これがマージソート (merge sort) の原理です。次の図を見てください。
9 5 3 7 6 4 2 8 最初の状態
|5 9|3 7|4 6|2 8| 長さ２の列に併合
|3 5 7 9|2 4 6 8| 長さ４の列に併合
2 3 4 5 6 7 8 9 ソート終了
図 : マージソート
マージをソートに応用する場合、最初は各要素をソート済みの配列 (リスト) として考えます。この状態で隣の配列とマージを行い、長さ 2 の配列を作ります。次に、この配列に対して再度マージを行い、長さ 4 の配列を作ります。このように順番にマージしていくと、最後には一つの配列にマージされソートが完了します。
それではプログラムを作りましょう。配列の長さを 1, 2, 4, 8, ... と増やしていくよりも、再帰的に考えた方が簡単です。マージは 2 つの列を一つの列にまとめる操作です。そこで、まずソートする配列を 2 つに分けて、前半部分をソートします。次に後半部分をソートして、その結果をマージすればいいわけです。
では、どうやってソートするのかというと、再帰呼び出しするのです。そうすると、どんどん配列を 2 つに割っていくことになり、最後にデータが一つとなります。それはソート済みの配列と考えることができるので、再帰呼び出しを終了してマージ処理に移ることができます。あとはデータを順番にマージしていってソートが完了します。
プログラムは次のようになります。
リスト : マージソート
# 挿入ソート
def insert_sort1(buff, low, high):
for i in xrange(low + 1, high + 1):
temp = buff[i]
j = i - 1
while j >= low and temp < buff[j]:
if temp >= buff[j]: break
buff[j + 1] = buff[j]
j -= 1
buff[j + 1] = temp
# マージソート
def merge_sort(buff, low, high):
if high - low <= LIMIT:
insert_sort1(buff, low, high)
else:
mid = (low + high) / 2
merge_sort(buff, low, mid)
merge_sort(buff, mid + 1, high)
#
p = 0
i = low
while i <= mid:
work[p] = buff[i]
p += 1
i += 1
i = mid + 1
j = 0
k = low
while i <= high and j < p:
if work[j] <= buff[i]:
buff[k] = work[j]
k += 1
j += 1
else:
buff[k] = buff[i]
k += 1
i += 1
while j < p:
buff[k] = work[j]
k += 1
j += 1
最初に区間の幅が LIMIT 以下になったかチェックします。そうであれば、挿入ソート (insert_sort1) に切り替えてソートします。この方が少しですが速くなります。これが再帰呼び出しの停止条件になります。区間の幅が LIMIT よりも大きい場合はマージソートを行います。
まず列の中央を求めて変数 mid にセットします。最初に前半部、それから後半部をマージソートします。これは merge_sort を再帰呼び出しするだけです。再帰呼び出しから戻ってくると、配列の前半部分と後半部分はソートされているのでマージ処理を行います。
まず前半部分を作業領域 work に退避します。work はグローバル変数として定義します。work の大きさはソートする配列の半分で十分です。たとえば、前半部分のデータよりも後半部分のデータがすべて小さいとします。この場合、後半部分のデータが先頭から順番にセットされ、その後ろに退避した前半部分のデータがセットされます。逆に、前半部分のデータがすべて小さければ、後半部分のデータは移動する必要はないので、work に退避した前半部分のデータを元に戻すことになります。
次の while ループで、前半部分もしくは後半部分どちらかにデータがある間、データの比較と移動を繰り返し行います。前半部分と後半部分を先頭から順番に比較し、小さい方を区間の先頭から順番にセットしていきます。後半部分のデータが先になくなって、作業領域 work にデータが残っている場合は、最後の while ループでデータを後ろに追加します。
それでは実行結果を示します。
表 : merge sort の結果 (単位 : 秒) 個数 乱数 昇順 逆順 山型 ----------------------------------- 1000 : 0.009 0.005 0.009 0.007 2000 : 0.020 0.012 0.019 0.016 4000 : 0.043 0.026 0.040 0.034 8000 : 0.095 0.058 0.087 0.074 16000 : 0.203 0.123 0.184 0.158 32000 : 0.437 0.265 0.393 0.338 実行環境 : Windows XP, celeron 1.40 GHz, Python 2.4.2
マージソートの実行時間は、要素数を n とすると平均して n * log n に比例します。マージソートはクイックソートと同様に高速なアルゴリズムですが、実際にプログラムを作って比較してみるとクイックソートの方が高速です。しかし、マージソートは配列を単純に二分割していくため、クイックソートと違ってデータの種類によって性能が劣化することはありません。ヒープソートと同様に、どのようなデータに対しても力を発揮してくれるわけです。ただし、ヒープソートとは違って作業領域が必要になります。
なお、マージソートは連結リストのソートや外部ソートに適したアルゴリズムです。連結リストのソートは次回に取り上げることにしましょう。
ご参考までにＣ言語のプログラムと実行時間を示します
リスト : Ｃ言語のプログラム
/* ヒープソート */
void heap_sort(int *buff, int size)
{
int i, n, c, x;
for(i = size / 2 - 1; i >= 0; i--){
n = i;
x = buff[n];
while((c = 2 * n + 1) < size){
if(c + 1 < size && buff[c] < buff[c + 1]) c++;
if(x >= buff[c]) break;
buff[n] = buff[c];
n = c;
}
buff[n] = x;
}
for(i = size - 1; i >= 0; i--){
x = buff[i];
buff[i] = buff[0];
n = 0;
while((c = 2 * n + 1) < i){
if(c + 1 < i && buff[c] < buff[c + 1]) c++;
if(x >= buff[c]) break;
buff[n] = buff[c];
n = c;
}
buff[n] = x;
}
}
/* マージソート (work を確保すること) */
/* 挿入ソート */
void insert_sort1(int *buff, int low, int high)
{
int i;
for(i = low + 1; i <= high; i++){
int j, temp = buff[i];
for(j = i - 1; j >= low && temp < buff[j]; j--){
buff[j + 1] = buff[j];
}
buff[j + 1] = temp;
}
}
/* マージソート */
void merge_sort(int *buff, int low, int high)
{
if(high - low <= LIMIT){
insert_sort1(buff, low, high);
} else {
int mid = (low + high) / 2;
int i, j, k, p;
merge_sort(buff, low, mid);
merge_sort(buff, mid + 1, high);
p = 0;
i = low;
while(i <= mid) work[p++] = buff[i++];
i = mid + 1;
j = 0;
k = low;
while(i <= high && j < p){
if(work[j] <= buff[i]){
buff[k++] = work[j++];
} else {
buff[k++] = buff[i++];
}
}
while(j < p) buff[k++] = work[j++];
}
}
表 : heap sort の結果 (単位 : 秒) 個数 乱数 昇順 逆順 山型 ------------------------------------- 500000 : 0.204 0.094 0.094 0.109 1000000 : 0.547 0.203 0.203 0.234 2000000 : 1.422 0.437 0.437 0.484 4000000 : 3.594 0.906 0.922 1.047 表 : merge sort の結果 (単位 : 秒) 個数 乱数 昇順 逆順 山型 ------------------------------------- 500000 : 0.141 0.062 0.079 0.063 1000000 : 0.297 0.125 0.172 0.157 2000000 : 0.609 0.266 0.360 0.344 4000000 : 1.312 0.610 0.781 0.703 実行環境 : Windows XP, celeron 1.40 GHz, Borland C++ 5.5.1 for Win32
今まで説明したソートは、要素を比較して適切な位置に移動することでソートを行ってきました。ところが、要素の性質によっては比較しなくてもソートすることができます。たとえば、トランプの札をソートすることを考えてみましょう。手作業で行う場合、1 の札はここ、2 の札はここ、3 の札はここ、というように置く場所を決めて札を分けていきます。そして、最後に 1 の札から順番に並べればソートが済んだことになります。
一般には、要素のキーの種類だけ入れ物（ビン）を用意して、要素をキーに対応するビンに入れていきます。キーはソートしようとする要素の性質を表します。トランプでいえば、1 から 13 という数字のことです。区分けが終了したらキーの小さい方からビンの内容を出力すればソートが完了することになります。これを「ビンソート (bin sort) 」とか「バケットソート (bucket sort) 」といいます。ビンソートの実行時間は要素数に比例します。
ビンソートを行う場合、キーの種類が限られた有限の値でなければソートすることはできません。トランプの場合、札が 1 から 13 までという限られた値しかないので簡単にソートすることができたのです。ここでは、ビンには複数のデータを入れることができるものとします。キーの種類がたくさんある場合はビンソートを簡単に使うことはできません。ところが、キーの特性をうまく使えば、種類がたくさんあってもビンソートを応用することができます。
簡単な例を示しましょう。2 桁の 10 進数をソートします。0 から 99 までの 100 個のビンは用意できないが、0 から 9 の 10 個のビンならば用意できると仮定します。現実的な話ではありませんが、説明のためということでご了承ください。もうおわかりかもしれませんが、1 の位と 10 の位の 2 回に分けてビンソートを行えば、全体をソートすることができます。これを「基数ソート (radix sort) 」といいます。次の図を見てください。
21 5 34 8 1 13 2 89 3 55
(1) 1 の位で分ける
ビン
[0] : [5] : 5 55
[1] : 21 1 [6] :
[2] : 2 [7] :
[3] : 13 3 [8] : 8
[4] : 34 [9] : 89
21 1 2 13 3 34 5 55 8 89
(2) 10 の位で分ける
ビン
[0] : 1 2 3 5 8 [5] : 55
[1] : 13 [6] :
[2] : 21 [7] :
[3] : 34 [8] : 89
[4] : [9] :
1 2 3 5 8 13 21 34 55 89 ソート完了
図 : 基数ソート
まず 1 の位でビンソートを行ないます。順番にビンに入れていくので、ビンのなかの整数の順序はビンに入れる前の順序と同じです。ビンから取り出して並べると、1 の位でソートされた状態になります。ビンから取り出すときも、最初に入れた要素から取り出していくことに注意してください。。
次に 10 の位でビンソートを行ないます。すでに 1 の位でソートされているので、各ビンには小さい順番で整数が並んでいきます。最後に小さいビンから出力すればソートが完了します。
それでは、具体的にどのようにプログラムすればよいのでしょうか。ビンのサイズはデータを調べてみないとわかりません。連結リストなどのデータ構造を使ってビンを実現することもできますが、もっと単純な方法があります。それは「度数分布表」を使う方法です。この方法を「分布数えソート (distribution counting sort) 」といいます。
度数分布表とはキーの要素数を数え上げた表のことです。そして、度数分布表の左から右へ要素を順番に足し合わせたものを「累積度数表」といいます。この表を使うと要素を順番に並べることができます。先ほどの例をあてはめてみましょう。まず、1 の位に対しての度数分布表を作ります。
21 5 34 8 1 13 2 89 3 55
度数分布表
0 1 2 3 4 5 6 7 8 9
T1[ 0 2 1 2 1 2 0 0 1 1 ]
図 : 度数分布表の作成
この表を作るのは簡単ですね。1 の位を配列の添字に対応させて、対応する配列の要素を 1 増やしていくだけです。もちろん、配列の要素は 0 に初期化しておくことをお忘れなく。次は累積度数表に変換します。これも簡単で、添字 0 から順番に足していくだけです。
累積度数表に変換
0 1 2 3 4 5 6 7 8 9
T2[ 0 2 3 5 6 8 8 8 9 10 ]
図 : 累積度数表の作成
この表は 0 からそのキーまでの要素の合計数を表しています。したがって、1 の位が n のデータは、配列の (T2[n] - T1[n]) 番目から (T2[n] - 1) 番目に配置されることになります。たとえば、1 の位が 5 の場合、T1[5] = 2, T2[5] = 8 なので、6, 7 番目に配置されます。そこで、作業用の配列を用意して累積度数表の示す位置にデータを配置していけば、1 の位でソートしたことになります。次の図を見てください。
作業用配列
セットする順番
0 : 21 [10]
1 : 1 [6]
2 : 2 <--(T2[2] -= 1)の示す位置にセット [4]
3 : 13 <--(T2[3] -= 1)の示す位置にセット [5]
4 : 3 <--(T2[3] -= 1)の示す位置にセット [2]
5 : 34 [8]
6 : 5 [9]
7 : 55 <--(T2[5] -= 1)の示す位置にセット [1]
8 : 8 [7]
9 : 89 <--(T2[9] -= 1)の示す位置にセット [3]
21 5 34 8 1 13 2 89 3 55 元のデータ
21 1 2 13 3 34 5 55 8 89 1 の位でソート完了
図 : 作業用配列へのセット
作業用配列には、ソート前の配列の後ろ側からデータを取り出してセットしていきます。これは、同じ値が複数ある場合、その順番を変えないようにするためです。そうしないと、基数ソートは動作しません。また、これで基数ソートは安定なソートになります。
データは T2[n] - 1 の位置にセットし、そのあとで T2[n] の値を一つ減らします。そうしないと、複数の値があると同じ位置に書き込んでしまいます。プログラムでは、T2[n] の値を -1 (T2[n] -= 1) してから、その位置にデータを書き込めばいいわけです。
次に、10 の位に対して同様に分布数えソートを行えば基数ソートは完了します。下図を参考にしてください。
度数分布表
0 1 2 3 4 5 6 7 8 9
T1[ 5 1 1 1 0 1 0 0 1 0 ]
累積度数表に変換
0 1 2 3 4 5 6 7 8 9
T2[ 5 6 7 8 8 9 9 9 10 10 ]
作業メモリ
セットする順番
0 : 1 [9]
1 : 2 [8]
2 : 3 [6]
3 : 5 <----(T2[0] -= 1)の示す位置にセット [4]
4 : 8 <----(T2[0] -= 1)の示す位置にセット [2]
5 : 13 [7]
6 : 21 [10]
7 : 34 [5]
8 : 55 <----(T2[5] -= 1)の示す位置にセット [3]
9 : 89 <----(T2[8] -= 1)の示す位置にセット [1]
21 1 2 13 3 34 5 55 8 89 1 の位でソートしたデータ
1 2 3 5 8 13 21 34 55 89 ソート完了
図 : 10 の位のソート
このように、下位の桁 (右の桁) からソートしていく方法を「直接基数法 (straight radix sort) 」と呼びます。逆に、上位の桁 (左の桁) からソートしていく方法もあります。これを「基数交換法 (radix exchange sort) 」と呼びます。最下位桁 (Least Significant Digit) を LSD, 最上位桁 (Most Significant Digit) を MSD と呼ぶことから、LSD radix sort, MSD radix sort と呼ぶ場合もあります。基数交換法についてはあとで詳しく説明します。
それでは、基数ソート (直接基数法) のプログラムを作りましょう。ここでは、整数値の範囲を 0 から 4294967295 (32 bit 無符号整数) に限定します。この場合、10 進数では 10 桁になりますが、256 進数で考えると 4 桁と少なくなります。また、各桁の値はビット操作で簡単に求めることができるので便利です。
プログラムは次のようになります。
リスト : 基数ソート (直接基数法)
def radix_sort(buff):
size = len(buff)
work = [0] * size
count = [0] * 256
for i in xrange(4):
shift = i * 8
for x in xrange(256): count[x] = 0
for x in xrange(size):
count[(buff[x] >> shift) & 0xff] += 1
for x in xrange(256):
count[x] += count[x - 1]
for x in xrange(size - 1, -1, -1):
y = (buff[x] >> shift) & 0xff
cumul[y] -= 1
work[cumul[y]] = buff[x]
temp = buff
buff = work
work = temp
基数ソートはマージソートと同様に作業用の配列が必要になります。ここでは、buff と同じサイズの配列 work を用意します。度数分布表と累積度数表は配列 count を使って作成します。count の大きさは 256 になります。
次に、for ループで下位の桁から分布数えソートを行います。変数 shift はビットシフト用の変数で、0, 8, 16, 24 と 8 ビットずつ増やしていきます。まず最初に、count を 0 に初期化します。そして、次の for ループで度数分布表を作成します。取り出す桁に合わせて右ビットシフトして 0xff とアンドをとれば、その桁の値を求めることができます。それから、count の要素を加算して累積度数表を作成します。これも簡単ですね。
最後の for ループで、累積度数表の示す位置にデータをセットします。このとき、最初に累積度数表の値をデクリメントしておくことをお忘れなく、すべてのデータをセットしたら、work と buff を交換します。あとはこれを 4 回繰り返すだけです。交換する回数は偶数なので、ソートされたデータは引数として渡された配列にセットされます。
それでは実行結果を示します。
表 : radix sort の結果 (単位 : 秒) 個数 乱数 昇順 逆順 山型 ----------------------------------- 1000 : 0.006 0.005 0.005 0.005 2000 : 0.010 0.010 0.010 0.010 4000 : 0.020 0.020 0.020 0.020 8000 : 0.041 0.039 0.039 0.039 16000 : 0.081 0.078 0.078 0.078 32000 : 0.162 0.156 0.157 0.156 実行環境 : Windows XP, celeron 1.40 GHz, Python 2.4.2
乱数データと山型データの場合、基数ソートの方がクイックソートよりも速くなりました。とくに、データ数が多くなると、その差が大きくなります。
キーを m 個に分割した場合、基数ソートは分布数えソートを m 回繰り返し実行する必要があります。したがって、要素数を n とすると実行時間は m * n に比例します。しかし、m が n に比べて十分に小さい場合は、基数ソートの実行時間は n に比例すると考えることができます。実際、今回の実行結果を見ると、要素数が 2 倍になると実行時間も約 2 倍になっていることがわかります。
次は基数交換法のプログラムを作りましょう。基数交換法は上位の桁からソートしますが、この場合は再帰呼び出しを使うと簡単です。次の図を見てください。
21 5 ↑ 1
5 8 │ 2
34 1 0x のデータ ==> 3
8 2 │ 5
1 3 ↓ 8
13 ==> 13 1x のデータ 13 (ソート済み)
2 21 2x のデータ 21 (ソート済み)
89 34 3x のデータ 34 (ソート済み)
3 55 5x のデータ 55 (ソート済み)
55 89 8x のデータ 89 (ソート済み)
下のデータ 10 の位でソート 1 の位でソート
図 : 基数交換法
最初に 10 の位で分布数えソートします。すると、10 の位が等しいデータが集まるので、次は等しいデータの区間を 1 の位で分布数えソートします。上図の場合、0 のデータが 0 番目から 4 番目の範囲にあります。今度は区間 (0, 4) にあるデータを 1 の位で分布数えソートします。この処理は再帰呼び出しを使うと簡単に実現できます。10 の位が 1, 2, 3, 5, 8 のデータは 1 つしかないので、1 の位でソートする必要はありません。
プログラムは次のようになります。
リスト : 基数ソート (基数交換法)
def radix_sort1(buff, low, high, n = 3):
if high - low <= LIMIT:
insert_sort1(buff, low, high)
else:
count = [0] * 257
shift = n * 8
for i in xrange(low, high + 1):
count[(buff[i] >> shift) & 0xff] += 1
for i in xrange(1, 256):
count[i] += count[i - 1]
for i in xrange(high, low - 1, -1):
c = (buff[i] >> shift) & 0xff
count[c] -= 1
work[count[c] + low] = buff[i]
for i in xrange(low, high + 1):
buff[i] = work[i]
if n > 0:
count[256] = high - low + 1
for i in xrange(0, 256):
l = low + count[i]
h = low + count[i + 1] - 1
if l < h: radix_sort1(buff, l, h, n - 1)
関数 radix_sort1 の引数 low, high がソートする区間を表します。引数 n が分布数えソートを行う桁数を表します。最初に、区間 (low, high) が LIMIT (10) よりも小さい場合は挿入ソート (insert_sort1) に切り替えます。この方が少しですが速くなります。そうでなければ、分布数えソートを行います。これは今までとほとんど同じですが、区間が (low, high) であることと、ソートしたあとで work から buff へデータをコピーしているところが違います。ご注意ください。
最後に、n が 0 より大きい場合は、次の桁をソートするため radix_sort1 を再帰呼び出しします。桁の値 (0 - 255) を i とすると、その区間は low + count[i] から low + count[i + 1] - 1 までになります。count は累積度数表ですが、データをセットするときにデクリメントされていくため、count[i] は区間の始点に、count[i + 1] - 1 は区間の終点になることに注意してください。
それでは実行結果を示します。
表 : 基数交換法の結果 (単位 : 秒) 個数 乱数 昇順 逆順 山型 ----------------------------------- 1000 : 0.007 0.007 0.007 0.007 2000 : 0.014 0.013 0.013 0.013 4000 : 0.040 0.026 0.026 0.025 8000 : 0.090 0.051 0.051 0.049 16000 : 0.140 0.102 0.102 0.098 32000 : 0.238 0.204 0.203 0.198 実行環境 : Windows XP, celeron 1.40 GHz, Python 2.4.2
直接基数法よりも少し遅くなりましたが、乱数データと山型データはクイックソートよりも速くなりました。ところで、基数交換法 (MSD radix sort) は文字列のソートにも応用することができます。これは次回で取り上げることにしましょう。
ところで、基数交換法は 2 進数を基準に行うこともできます。これを「２進基数交換法」といいます。2 進数で考えると、桁の値は 0 と 1 しかありません。ビットが 0 のデータを前半に、ビットが 1 のデータを後半に分割していけば、データをソートすることができます。データの分割はクイックソートと同様に、左から 1 のデータを探し、右から 0 のデータを探して、それを交換することで実現できます。したがって、今までの基数ソートとは違って、作業用のメモリ領域は必要ありません。そのかわり、２進基数交換法は不安定なソートになります。
プログラムは次のようになります。
リスト : 基数ソート (2 進基数交換法)
def radix_sort2(buff, low, high, n = 0x80000000):
if high - low <= LIMIT:
insert_sort1(buff, low, high)
else:
i = low
j = high
while True:
while i <= j and buff[i] & n == 0: i += 1
while i <= j and buff[j] & n > 0: j -= 1
if i > j: break
temp = buff[i]
buff[i] = buff[j]
buff[j] = temp
i += 1
j -= 1
if n > 1:
radix_sort2(buff, low, j, n >> 1)
radix_sort2(buff, i, high, n >> 1)
関数 radix_sort2 の引数 low, high がソートする区間を表します。引数 n がチェックするビットを表します。最初に、区間 (low, high) が LIMIT (10) よりも小さい場合は挿入ソート (insert_sort1) に切り替えます。この方が少しですが速くなります。そうでなければ、区間 (low, high) をビット 0 と 1 で二分割します。
分割方法はクイックソートとほとんど同じです。2 番目の while ループで、左側からビット 1 の要素を探します。ここではビットが 0 の間は探索位置を進める、というように置き換えています。同様に次の while ループで右側からビット 0 の要素を探します。クイックソートとは違って、i <= j のチェックが必要なことに注意してください。お互いの探索位置 i と j が交差したら分割は終了です。break 文で while ループから脱出します。そうでなければお互いの要素を交換します。あとは、分割した区間に対して radix_sort2 を再帰呼び出しするだけです。
それでは実行結果を示します。
表 : radix sort の結果 (単位 : 秒) 個数 乱数 昇順 逆順 山型 ----------------------------------- 1000 : 0.020 0.021 0.022 0.024 2000 : 0.041 0.043 0.044 0.049 4000 : 0.087 0.086 0.087 0.098 8000 : 0.181 0.171 0.174 0.201 16000 : 0.376 0.342 0.348 0.400 32000 : 0.783 0.686 0.697 0.806 実行環境 : Windows XP, celeron 1.40 GHz, Python 2.4.2
実行速度は分布数えソートを使った基数交換法 (radix_sort1) やクイックソートよりもずいぶんと遅くなりました。ビット操作が得意なＣ言語を使うと、もう少し速くなるかもしれません。
ご参考までにＣ言語のプログラムと実行時間を示します
リスト : Ｃ言語のプログラム
/* 直接基数法 (LSD radix sort) */
void radix_sort(unsigned int *buff, int size)
{
int count[256];
int i, j;
unsigned int *temp;
for(i = 0; i < 32; i += 8){
for(j = 0; j < 256; j++) count[j] = 0;
for(j = 0; j < size; j++) count[(buff[j] >> i) & 0xff]++;
for(j = 1; j < 256; j++) count[j] += count[j - 1];
for(j = size - 1; j >= 0; j--){
work[--count[(buff[j] >> i) & 0xff]] = buff[j];
}
temp = buff;
buff = work;
work = temp;
}
}
/* 基数交換法 (MSD radix sort) */
void radix_sort1(unsigned int *buff, int low, int high, int n)
{
if(high - low <= LIMIT){
insert_sort1(buff, low, high);
} else {
int count[257];
int shift = n * 8;
int i;
for(i = 0; i < 257; i++) count[i] = 0;
for(i = low; i <= high; i++) count[(buff[i] >> shift) & 0xff]++;
for(i = 1; i < 256; i++) count[i] += count[i - 1];
for(i = high; i >= low; i--){
work[--count[(buff[i] >> shift) & 0xff] + low] = buff[i];
}
for(i = low; i <= high; i++) buff[i] = work[i];
if(n > 0){
count[256] = high - low + 1;
for(i = 0; i < 256; i++){
int l = low + count[i];
int h = low + count[i + 1] - 1;
if(l < h) radix_sort1(buff, l, h, n - 1);
}
}
}
}
/* 2 進基数交換法 */
void radix_sort2(unsigned int *buff, int low, int high, unsigned int n)
{
if(high - low <= LIMIT){
insert_sort1(buff, low, high);
} else {
int i = low;
int j = high;
while(TRUE){
int temp;
while(i <= j && !(buff[i] & n)) i++;
while(i <= j && buff[j] & n) j--;
if(i > j) break;
temp = buff[i];
buff[i] = buff[j];
buff[j] = temp;
i++;
j--;
}
if(n > 1){
radix_sort2(buff, low, j, n >> 1);
radix_sort2(buff, i, high, n >> 1);
}
}
}
表 : radix_sort の結果 (単位 : 秒) 個数 乱数 昇順 逆順 山型 ------------------------------------- 500000 : 0.047 0.047 0.047 0.047 1000000 : 0.093 0.109 0.094 0.094 2000000 : 0.172 0.203 0.203 0.203 4000000 : 0.344 0.406 0.407 0.407 表 : radix_sort1 の結果 (単位 : 秒) 個数 乱数 昇順 逆順 山型 ------------------------------------- 500000 : 0.047 0.063 0.062 0.063 1000000 : 0.110 0.125 0.125 0.125 2000000 : 0.235 0.235 0.235 0.234 4000000 : 0.547 0.485 0.469 0.469 表 : radix_sort2 の結果 (単位 : 秒) 個数 乱数 昇順 逆順 山型 ------------------------------------- 500000 : 0.109 0.047 0.047 0.063 1000000 : 0.204 0.094 0.109 0.125 2000000 : 0.422 0.312 0.250 0.265 4000000 : 0.890 0.640 0.547 0.532 実行環境 : Windows XP, celeron 1.40 GHz, Borland C++ 5.5.1 for Win32