整列 (sorting) の続きです。今回はヒープソート、マージソート、分布数えソート、基数ソート (直接基数法と基数交換法) について説明します。
ヒープ (heap) は拙作のページ「二分木とヒープ」で説明したデータ構造です。実は、このヒープを使ったソートも優秀なアルゴリズムの一つです。実行時間は N * log2 N に比例しますが、平均するとクイックソートよりも遅くなります。しかし、クイックソートとは違って、データの種類によって性能が劣化することはありません。
プログラムは次のようになります。
リスト : ヒープソート
def heap_sort(buff):
# ヒープの構成
size = len(buff)
for i in range(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 range(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 で管理されていて、その値は一つずつ減っていくことに注意してください。
それでは実行結果を示します。
表 : ヒープソート (単位 : 秒) 個数: 乱数 : 昇順 : 逆順 : 山型 -----+-------+-------+-------+------- 1000: 0.002 : 0.003 : 0.004 : 0.002 2000: 0.005 : 0.007 : 0.005 : 0.005 4000: 0.017 : 0.022 : 0.011 : 0.021 8000: 0.037 : 0.035 : 0.022 : 0.024 16000: 0.073 : 0.086 : 0.048 : 0.068 32000: 0.169 : 0.156 : 0.139 : 0.144 64000: 0.266 : 0.279 : 0.226 : 0.279
実行環境: Python 3.8.10, Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz
このように、ヒープソートはどのデータに対しても、そこそこの速度でソートすることができます。ただし、実行時間はクイックソートよりも遅くなりました。参考文献『Ｃプログラマのためのアルゴリズムとデータ構造』によると、ヒープソートの速度はクイックソートの半分くらいといわれています。ヒープソートの処理内容はクイックソートよりも複雑なので、時間がかかるのは仕方がないところでしょう。
マージ（併合 : 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 をセットする
データがなくなるまで繰り返す
図 1 : マージの考え方
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 : マージソート
マージをソートに応用する場合、最初は各要素をソート済みの配列 (リスト) として考えます。この状態で隣の配列とマージを行い、長さ 2 の配列を作ります。次に、この配列に対して再度マージを行い、長さ 4 の配列を作ります。このように順番にマージしていくと、最後には一つの配列にマージされソートが完了します。
それではプログラムを作りましょう。配列の長さを 1, 2, 4, 8, ... と増やしていくよりも、再帰的に考えた方が簡単です。マージは 2 つの列を一つの列にまとめる操作です。そこで、まずソートする配列を 2 つに分けて、前半部分をソートします。次に後半部分をソートして、その結果をマージすればいいわけです。
では、どうやってソートするのかというと、再帰呼び出しするのです。そうすると、どんどん配列を 2 つに割っていくことになり、最後にデータが一つとなります。それはソート済みの配列と考えることができるので、再帰呼び出しを終了してマージ処理に移ることができます。あとはデータを順番にマージしていってソートが完了します。
プログラムは次のようになります。
リスト : マージソート
# 挿入ソート
def insert_sort1(buff, low, high):
for i in range(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
def msort(buff):
global work
work = [0] * (len(buff) // 2)
merge_sort(buff, 0, len(buff) - 1)
最初に区間の幅が LIMIT 以下になったかチェックします。そうであれば、挿入ソート (insert_sort1) に切り替えてソートします。この方が少しですが速くなります。これが再帰呼び出しの停止条件になります。区間の幅が LIMIT よりも大きい場合はマージソートを行います。
まず列の中央を求めて変数 mid にセットします。最初に前半部、それから後半部をマージソートします。これは merge_sort() を再帰呼び出しするだけです。再帰呼び出しから戻ってくると、配列の前半部分と後半部分はソートされているのでマージ処理を行います。
まず前半部分を作業領域 work に退避します。work はグローバル変数として定義します。work の大きさはソートする配列の半分で十分です。たとえば、前半部分のデータよりも後半部分のデータがすべて小さいとします。この場合、後半部分のデータが先頭から順番にセットされ、その後ろに退避した前半部分のデータがセットされます。逆に、前半部分のデータがすべて小さければ、後半部分のデータは移動する必要はないので、work に退避した前半部分のデータを元に戻すことになります。
次の while ループで、前半部分もしくは後半部分どちらかにデータがある間、データの比較と移動を繰り返し行います。前半部分と後半部分を先頭から順番に比較し、小さい方を区間の先頭から順番にセットしていきます。後半部分のデータが先になくなって、作業領域 work にデータが残っている場合は、最後の while ループでデータを後ろに追加します。
それでは実行結果を示します。
表 : マージソート (単位 : 秒) 個数: 乱数 : 昇順 : 逆順 : 山型 -----+-------+-------+-------+------- 1000: 0.003 : 0.001 : 0.002 : 0.002 2000: 0.005 : 0.003 : 0.005 : 0.004 4000: 0.013 : 0.006 : 0.011 : 0.008 8000: 0.033 : 0.020 : 0.037 : 0.017 16000: 0.051 : 0.027 : 0.050 : 0.037 32000: 0.124 : 0.063 : 0.114 : 0.102 64000: 0.277 : 0.141 : 0.260 : 0.174
マージソートの実行時間は、要素数を N とすると平均して N * log2 N に比例します。マージソートはクイックソートと同様に高速なアルゴリズムですが、実際にプログラムを作って比較してみるとクイックソートの方が高速です。しかし、マージソートは配列を単純に二分割していくため、クイックソートと違ってデータの種類によって性能が劣化することはありません。ヒープソートと同様に、どのようなデータに対しても力を発揮してくれるわけです。ただし、ヒープソートとは違って作業領域が必要になります。
なお、マージソートは連結リストのソートや外部ソートに適したアルゴリズムです。連結リストのソートは次回に取り上げることにしましょう。
マージソートは、配列 buff の大きさを N とすると、大きさが N / 2 の作業用領域 work を必要としました。ここで、作業領域 work の大きさを配列 buff と同じ N にすることを考えます。この場合、最初に buff を work にコピーしておいて、再帰のたびに buff と work を交互に入れ換えることで、マージソートの実行速度を改善することができます。
なお、この方法は『C++によるソート(sort)のページ』の「修正マージソート」を参考にさせていただきました。同ページによると、『修正マージソートは、Java のクラス型のソートに採用されています。』 とのことです。有用な情報を公開されている作者様に感謝いたします。
プログラムは次のようになります。
リスト : 改良版マージソート
def merge_sort1(a, b, low, high):
if high - low <= LIMIT:
insert_sort1(b, low, high)
else:
mid = (low + high) // 2
merge_sort1(b, a, low, mid)
merge_sort1(b, a, mid + 1, high)
i = low
j = mid + 1
k = low
while i <= mid and j <= high:
if a[i] <= a[j]:
b[k] = a[i]
i += 1
else:
b[k] = a[j]
j += 1
k += 1
while i <= mid:
b[k] = a[i]
k += 1
i += 1
while j <= high:
b[k] = a[j]
k += 1
j += 1
def msort1(buff):
work = buff[:]
k = len(buff)
merge_sort1(work, buff, 0, k - 1)
msort1() は buff をコピーした配列 work を生成し、それを merge_sort1() に渡してマージソートします。merge_sort1(a, b, low, high) は、配列 b の区間 (low, high) を二分割してソートします。merge_sort1() を再帰呼び出しするとき、引数 a, b を逆にすることに注意してください。
二つの区間をソートしたあと、二つの区間をマージした結果は配列 a の区間 (low, high) にセットします。改良前の merge_sort() では、あらかじめ buff の前半部分を work に退避していましたが、buff を work にコピーしておいて、buff と work を交互に切り替えることで、buff の前半部分を work に退避する処理が不要になります。
それでは実行結果を示します。
表 : 改良版マージソート (単位 : 秒) 個数: 乱数 : 昇順 : 逆順 : 山型 -----+-------+-------+-------+------- 8000: 0.022 : 0.015 : 0.017 : 0.015 16000: 0.053 : 0.034 : 0.036 : 0.032 32000: 0.113 : 0.062 : 0.098 : 0.076 64000: 0.200 : 0.150 : 0.168 : 0.161
結果を見ればお分かりのように、昇順データ以外では改良版のほうが速くなりました。改良の効果は十分に出ていると思います。メモリを多く使用することになりますが、このような簡単な方法でマージソートを改良できるとは驚きました。
今まで説明したソートは、要素を比較して適切な位置に移動することでソートを行ってきました。ところが、要素の性質によっては比較しなくてもソートすることができます。たとえば、トランプの札をソートすることを考えてみましょう。手作業で行う場合、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 ソート完了
図 3 : 基数ソート
まず 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 ]
図 4 : 度数分布表の作成
この表を作るのは簡単ですね。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 ]
図 5 : 累積度数表の作成
この表は 0 からそのキーまでの要素の合計数を表しています。したがって、1 の位が n のデータは、配列の (T2[n] - T1[n]) 番目から (T2[n] - 1) 番目に配置されることになります。たとえば、1 の位が 5 の場合、T1[5] = 2, T2[5] = 8 なので、6, 7 番目に配置されます。そこで、作業用の配列を用意して累積度数表の示す位置にデータを配置していけば、1 の位でソートしたことになります。図 6 を見てください。
作業用配列
セットする順番
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 の位でソート完了
図 6 : 作業用配列へのセット
作業用配列には、ソート前の配列の後ろ側からデータを取り出してセットしていきます。これは、同じ値が複数ある場合、その順番を変えないようにするためです。そうしないと、基数ソートは動作しません。また、これで基数ソートは安定なソートになります。
データは 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 ソート完了
図 7 : 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 range(4):
shift = i * 8
for x in range(256): count[x] = 0
for x in range(size):
count[(buff[x] >> shift) & 0xff] += 1
for x in range(1, 256):
count[x] += count[x - 1]
for x in range(size - 1, -1, -1):
y = (buff[x] >> shift) & 0xff
count[y] -= 1
work[count[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 回繰り返すだけです。交換する回数は偶数なので、ソートされたデータは引数として渡された配列にセットされます。
それでは実行結果を示します。
表 : 基数ソート (単位 : 秒) 個数: 乱数 : 昇順 : 逆順 : 山型 -----+-------+-------+-------+------- 1000: 0.002 : 0.002 : 0.001 : 0.001 2000: 0.003 : 0.004 : 0.003 : 0.003 4000: 0.010 : 0.005 : 0.008 : 0.006 8000: 0.011 : 0.025 : 0.013 : 0.011 16000: 0.034 : 0.028 : 0.021 : 0.029 32000: 0.057 : 0.042 : 0.058 : 0.042 64000: 0.124 : 0.096 : 0.098 : 0.092
乱数データと山型データの場合、基数ソートの方がクイックソートよりも速くなりました。とくに、データ数が多くなると、その差が大きくなります。
キーを 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 の位でソート
図 8 : 基数交換法
最初に 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 range(low, high + 1):
count[(buff[i] >> shift) & 0xff] += 1
for i in range(1, 256):
count[i] += count[i - 1]
for i in range(high, low - 1, -1):
c = (buff[i] >> shift) & 0xff
count[c] -= 1
work[count[c] + low] = buff[i]
for i in range(low, high + 1):
buff[i] = work[i]
if n > 0:
count[256] = high - low + 1
for i in range(0, 256):
l = low + count[i]
h = low + count[i + 1] - 1
if l < h: radix_sort1(buff, l, h, n - 1)
def rsort1(buff):
global work
work = [0] * len(buff)
radix_sort1(buff, 0, len(buff) - 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.002 : 0.002 : 0.002 : 0.002 2000: 0.004 : 0.005 : 0.004 : 0.004 4000: 0.014 : 0.010 : 0.007 : 0.012 8000: 0.026 : 0.016 : 0.014 : 0.014 16000: 0.046 : 0.029 : 0.028 : 0.027 32000: 0.080 : 0.068 : 0.063 : 0.072 64000: 0.132 : 0.113 : 0.117 : 0.125
直接基数法よりも少し遅くなりましたが、山型データはクイックソートよりも速くなりました。ところで、基数交換法 (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)
def rsort2(buff):
radix_sort2(buff, 0, len(buff) - 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() を再帰呼び出しするだけです。
それでは実行結果を示します。
表 : ２進基数交換法 (単位 : 秒) 個数: 乱数 : 昇順 : 逆順 : 山型 -----+-------+-------+-------+------- 1000: 0.004 : 0.004 : 0.004 : 0.005 2000: 0.007 : 0.010 : 0.008 : 0.010 4000: 0.016 : 0.017 : 0.014 : 0.017 8000: 0.039 : 0.033 : 0.026 : 0.037 16000: 0.082 : 0.052 : 0.051 : 0.067 32000: 0.145 : 0.116 : 0.116 : 0.161 64000: 0.267 : 0.228 : 0.281 : 0.299
実行速度は分布数えソートを使った基数交換法 (radix_sort1) やクイックソートよりもずいぶんと遅くなりました。ビット操作が得意なＣ言語を使うと、もう少し速くなるかもしれません。