整列 (sorting) は、ある規則に従ってデータを順番に並べ換える操作です。たとえば、データが整数であれば大きい順に並べる、もしくは小さい順に並べます。一般に、このような操作を「ソート」と呼んでいます。ソートは昔から研究されている分野で、優秀なアルゴリズムが確立しています。このページでは単純なソートから高速なソートまで、いろいろなソートアルゴリズムを取り上げることにします。
ソートは大きく分けると、内部ソート (internal sort) と外部ソート (external sort) にわかれます。内部ソートはすべてのデータをメモリに読み込んでソートします。外部ソートはメモリにすべて読み込むことができない巨大なデータをソートするときに使われ、外部記憶装置に途中経過を記憶させながらソートします。
今回作成するプログラムは内部ソートで、データは整数値とします。データは配列 (Python ではリスト) に格納します。データは乱数のほかにも、山型データ (中央のデータがいちばん大きく端にいくほど小さいデータになる)、ソート済みのデータ (昇順)、逆順にソートされたデータ (降順) の 4 種類を用意して、実行時間を比較してみましょう。これらのデータは次のプログラムで簡単に作成することができます。
リスト : データの生成
def make_data(x):
# x は生成するデータの個数
# 乱数
a = [random.randint(0, 100000) for y in xrange(x)]
# 昇順
b = list(range(x))
# 降順
c = list(range(x, 0, -1))
# 山型
d = list(range(x // 2)) + list(range(x // 2, 0, -1))
return a, b, c, d
なお、プログラムの実行時間は、筆者のコーディング、実行したマシン、使用するプログラミング言語（またはコンパイラ）などの環境に大きく依存しています。また、これらの環境だけではなく、データの種類によっても実行時間は大きく左右されます。たとえば、高速なソートアルゴリズムとして有名な「クイックソート」の場合、データによっては実行時間が要素数の 2 乗に比例する最悪のケースが存在します。どのようなデータに対しても最速を誇るソートアルゴリズムは存在しません。興味のある方は、いろいろなデータをご自分の環境で試してみてください。
次に、ソートの安定性について説明します。安定 (stable) なソートとは、ソートキーが等しい場合、入力された順番が崩れないソートのことです。逆に、不安定なソートとは、入力された順番とは異なる結果になるソートのことです。図 1 を見てください。
2 番目の要素をキーにソートした場合、1 行目と 3 行目はソートキーが等しいですね。安定なソートであればソート結果が 1, 3, 2 の順番になり、入力時の位置関係が保たれています。不安定なソートはソート結果が、たとえば 3, 1, 2 の順番となり、入力時の位置関係が崩れます。
元のデータ 安定なソート 不安定なソート
--------------------------------------------------
(123, 'abc') (123, 'abc') (789, 'abc')
(456, 'def') (789, 'abc') (123, 'abc')
(789, 'abc') (456, 'def') (456, 'def')
図 1 : ソートの安定性
実用的なアプリケーションを作成する場合、ソートの安定性が重要になる場合があります。一般に、単純なソート（遅いソート）は安定で、複雑なソート（高速なソート）は安定ではない、という傾向があります。
最初は、単純なソートから説明しましょう。バブルソート (buble sort) は泡がぶくぶくと浮いてくるように、いちばん小さいデータが後ろから前に浮かび上がってくるアルゴリズムです。
隣接する 2 つのデータを比較して、順序が逆であれば入れ換えます。これを順番に後ろから前に行っていけば、いちばん小さなデータは頂上に浮かび上がっているというわけです。先頭が決まったならば、残りのデータに対して同じことを行えば、2 番目には残りのデータの中でいちばん小さいものが浮かび上がってきます。これをデータ数だけ繰り返せばソートが完了します。
9 5 3 7 6 4 8 交換しない
~~~
9 5 3 7 6 4 8 交換する
~~~
9 5 3 7 4 6 8 交換する
~~~
9 5 3 4 7 6 8 交換しない
~~~
9 5 3 4 7 6 8 交換する
~~~
9 3 5 4 7 6 8 交換する
~~~
3 9 5 4 7 6 8 いちばん小さいデータが決定する
+ 残りのデータに対して同様な操作を行う
図 2 : バブルソート
これをそのままプログラムすると次のようになります。
リスト : バブルソート
def buble_sort(buff):
k = len(buff) - 1
for i in xrange(k):
for j in xrange(k, i, -1):
if buff[j - 1] > buff[j]:
temp = buff[j]
buff[j] = buff[j - 1]
buff[j - 1] = temp
最初のループで k 回 (データの個数 - 1) だけ繰り返します。2 番目のループで buff の後ろから前に向かって、確定していないデータを比較していき、もしも順番が逆になっていたら交換します。とても簡単ですね。
それでは実行結果を示します。
表 : バブルソート (単位 : 秒) 個数: 乱数 : 昇順 : 逆順 : 山型 ----+-------+-------+-------+------- 1000: 0.089 : 0.047 : 0.097 : 0.071 2000: 0.314 : 0.174 : 0.433 : 0.317 4000: 1.283 : 0.698 : 1.661 : 1.165 8000: 4.953 : 2.812 : 6.497 : 4.630
実行環境: Python 3.8.10, Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz
バブルソートは簡単なアルゴリズムですが、データ数が多くなると時間がかかります。データ数を N とすると実行時間は N2 に比例します。バブルソートは安定なソートですが遅いアルゴリズムなのです。
挿入ソート (insert sort) は拙作のページ「新・お気楽 Python プログラミング入門第 2 回」で取り上げましたが、ここでも簡単に説明しておきましょう。
挿入ソートはソート済みの配列に新しいデータを挿入していくことでソートします。最初は先頭のデータひとつがソート済みと考え、2 番目のデータをそこに挿入することからスタートします。データを挿入するので、そこにあるデータをどかさないといけません。そこで、挿入位置を決めるため後ろから順番に比較するとき、いっしょにデータの移動も行うことにします。
[9] 5 3 7 6 4 8 5 を取り出す
[9] * 3 7 6 4 8 5 を[9]の中に挿入する
[5 9] 3 7 6 4 8 9 をひとつずらして先頭に 5 を挿入
[5 9] * 7 6 4 8 3 を取り出して[5 9]の中に挿入する
[3 5 9] 7 6 4 8 先頭に 3 を挿入
[3 5 9] * 6 4 8 7 を取り出して[3 5 9] に挿入
[3 5 7 9] 6 4 8 9 を動かして 7 を挿入
残りの要素も同様に行う
図 3 : 挿入ソート
プログラムは次のようになります。
リスト : 挿入ソート
def insert_sort(buff):
k = len(buff)
for i in range(1, k):
temp = buff[i]
j = i - 1
while j >= 0 and temp < buff[j]:
buff[j + 1] = buff[j]
j -= 1
buff[j + 1] = temp
最初のループで挿入するデータを選びます。ソート開始時は先頭のデータひとつがソート済みと考えるるので、2 番目のデータ（添字では 1）を取り出して挿入していきます。2 番目のループで挿入する位置を探しています。探索は後ろから前に向かって行います。このとき、挿入位置の検索と同時にデータの移動も行っています。ループが最後まで回れば、そのデータは先頭に挿入されることになります。
それでは実行結果を示します。
表 : 挿入ソート (単位 : 秒) 個数: 乱数 : 昇順 : 逆順 : 山型 ----+-------+-------+-------+------- 1000: 0.057 : 0.000 : 0.083 : 0.031 2000: 0.157 : 0.000 : 0.248 : 0.148 4000: 0.571 : 0.001 : 1.161 : 0.538 8000: 2.380 : 0.001 : 4.406 : 2.286
挿入ソートも実行時間はデータの個数の 2 乗に比例します。挿入ソートは遅いソートですが安定です。
ところで、このソートは興味深い特性をもっています。昇順（ソート済み）データの結果をみると、とても速いことがわかります。データがソートされていれば、2 番目のループは繰り返しを行わずに終了するため、最初のループの繰り返し回数でソートが完了することになります。したがって、与えられたデータが大まかにでもソートされていれば、2 番目のループで繰り返す回数が少なくなり、挿入ソートでも高速にソートすることができます。
選択ソート (selection sort) は、ソートしていないデータの中から最小値（または最大値）を見つけ、それを先頭のデータと交換する、という手順を繰り返すことでソートを行います。最初はすべてのデータの中から最小値を探し、それを配列の先頭 buff[0] と交換します。次は buff[1] 以降のデータの中から最小値を探し、それを buff[1] と交換します。これを繰り返すことでソートすることができます。
[9 5 3 7 6 4 8] 3 と 9 を交換する
+ +
3 [5 9 7 6 4 8] 5 と 4 を交換する
+ +
3 4 [9 7 6 5 8] 9 と 5 を交換する
+ +
3 4 5 [7 6 9 8] 7 と 6 を交換する
+ +
3 4 5 6 [7 9 8] 7 と 7 を交換する
+
3 4 5 6 7 [9 8] 9 と 8 を交換してソート終了
+ +
図 4 : 選択ソート
このように、選択ソートは単純でわかりやすいアルゴリズムです。プログラムは次のようになります。
リスト : 選択ソート
def select_sort(buff):
k = len(buff)
for i in range(k - 1):
min = buff[i]
n = i
for j in range(i + 1, k):
if buff[j] < min:
min = buff[j]
n = j
buff[n] = buff[i]
buff[i] = min
データの個数を変数 k にセットします。最初のループで変数 i の値は 0 から k - 1 まで動きます。2 番目のループで buff[i] から buff[k - 1] までの中から最小値を探し、それを buff[i] と交換します。最小値とその位置は変数 min と n に格納します。2 番目のループを終了したら、buff[i] と buff[n] の値を交換します。
それでは実行結果を示します。
表 : 選択ソート (単位 : 秒) 個数: 乱数 : 昇順 : 逆順 : 山型 ----+-------+-------+-------+------- 1000: 0.036 : 0.039 : 0.029 : 0.035 : 2000: 0.106 : 0.106 : 0.114 : 0.116 : 4000: 0.423 : 0.410 : 0.513 : 0.449 : 8000: 1.637 : 1.626 : 2.100 : 1.758 :
選択ソートも実行時間はデータの個数の 2 乗に比例します。選択ソートは遅いソートですが安定です。
選択ソートと挿入ソートを比較すると、データの比較回数は挿入ソートのほうが少なくなり (平均すると約半分になる)、データの移動回数は選択ソートの方が少なくなります。今回は選択ソートの方が速くなりましたが、使用するプログラミング言語やデータの種類によっては、結果が異なる場合もあるでしょう。興味のある方はいろいろ試してみてください。
バブルソートは泡がぶくぶくと浮いてくるように、いちばん小さいデータが後ろから前へ浮かび上がってきます。シェーカーソート (shaker sort) は、いちばん小さなデータが浮かび上がるところはバブルソートと同じですが、その次はいちばん大きなデータを沈める操作を行います。そして、これ交互に繰り返すことでデータをソートします。つまり、双方向でパブルソートを行うわけです。次の図を見てください。
9 5 3 7 6 4 8 交換しない | 3 9 5 4 7 6 8 交換する
~~~ | + ~~~
9 5 3 7 6 4 8 交換する | 3 5 9 4 7 6 8 交換する
~~~ | + ~~~
9 5 3 7 4 6 8 交換する | 3 5 4 9 7 6 8 交換する
~~~ | + ~~~
9 5 3 4 7 6 8 交換しない | 3 5 4 7 9 6 8 交換する
~~~ | + ~~~
9 5 3 4 7 6 8 交換する | 3 5 4 7 6 9 8 交換する
~~~ | + ~~~
9 3 5 4 7 6 8 交換する | 3 5 4 7 6 8 9 決定
~~~ | + +
3 9 5 4 7 6 8 決定 |
+ |
図 5 : シェーカーソート
左側の図に小さなデータが浮かび上がってくる様子を、右側の図に大きなデータが沈んでいく様子を示します。あとは、これを繰り返すだけです。とても簡単ですね。
では、これで本当にバブルソートの性能を改善できるのでしょうか。答えはなんと NO なのです。これだけでは、実をいうと改善どころか改悪になってしまいます。シェーカーソートを有効に機能させるには、もうひとつ改良すべきポイントがあるのです。次の例を見てください。
4 5 6 7 8 9 3 交換する
~~~
・・省略・・
3 4 5 6 7 8 9 3 を決定
+
3 4 5 6 7 8 9 交換しない
+ ~~~
・・省略・・ 一度もデータを交換しない
3 4 5 6 7 8 9 4 を決定 => ソート終了
+ +
図 6 : ソートが終了する場合
この例の場合、3 を先頭に移動すればソートが完了しますね。バブルソートの場合、データの交換がまったく行われなければ、ソートは完了したと判断することができます。この例では 3 を先頭に移動したあと、さらにバブルソートを続けますが、データの交換は行われずに次のデータ 4 が決まりますね。ここでソートを終了してよいのです。
また、バブルソートの場合、最後にデータを交換した位置よりも前のデータはソート済みであることがわかります。したがって、その位置を記憶しておくことで、無駄な処理を省くことができます。シェーカーソートといっしょにこれらの改良方法もあとで試してみましょう。
このように、バブルソートはデータの並び方によって高速にソートできる場合があります。それでは、次のデータはどうなるのでしょうか。
9 4 5 6 7 8 3 交換する
~~~
・・省略・・
3 9 4 5 6 7 8 3 を決定
+
3 9 4 5 6 7 8 交換しない
+ ~~~
・・省略・・ データの交換は無い
3 9 4 5 6 7 8 データを交換するのでソートは終了しない
+ ~~~
図 7 : ソートが終了しない場合
先頭にいちばん大きなデータ 9 があるので、途中でソートを終了することはできません。ところが、ここで 9 を最後尾に移動させればソートが完了しますね。もうお気づきだと思いますが、このような場合シェーカーソートを使えばうまくいきます。データ 3 を決定したあと、シェーカーソートではいちばん大きなデータを沈めるので、データ 9 が最後尾に移動します。そのあと、今度はいちばん小さなデータを浮かべますが、データを交換することはないのでソートを終了することができる、というわけです。
たとえば、データ 9, 5, 3, 7, 6, 4, 8 をシェーカーソートすると、次のようになります。
9 5 3 7 6 4 8
3 9 5 4 7 6 8 3 を決定
+
3 5 4 7 6 8 9 9 を決定
+ +
3 4 5 6 7 8 9 4 を決定
+ + +
3 4 5 6 7 8 9 8 を決定、データ交換が無いので終了
+ + + +
図 8 : ソートが終了する場合
双方向でバブルソートすることにより、小さなデータは左側へ、大きなデータは右側へ移動していく様子がよくわかると思います。
まずはバブルソートの改良版から作りましょう。次のリストを見てください。
リスト : バブルソートの改良
def buble_sort(buff):
k = len(buff) - 1
while k >= 0:
j = -1
for i in range(1, k + 1):
if buff[i - 1] > buff[i]:
j = i - 1
temp = buff[j]
buff[j] = buff[i]
buff[i] = temp
k = j
改良版では、変数 k にデータを交換した位置を記憶しておきます。k の値が -1 であれば、データは一度も交換されなかったのでソートを終了します。
次はシェーカーソートを作ります。
リスト : シェーカーソート
def shaker_sort(buff):
low = 0
high = len(buff) - 1
j = -1
while low < high:
for i in range(low, high):
if buff[i] > buff[i + 1]:
temp = buff[i]
buff[i] = buff[i + 1]
buff[i + 1] = temp
j = i
high = j
for i in range(high, low, -1):
if buff[i - 1] > buff[i]:
temp = buff[i - 1]
buff[i - 1] = buff[i]
buff[i] = temp
j = i
low = j
変数 low と high はソートする区間を表します。low より前のデータと high より後ろのデータはソート済みです。low < hight ならばデータがあるのでソートを続けます。データを交換した位置は変数 j に記憶しておきます。
前半の for ループが大きなデータを沈める処理で、後半の for ループが小さなデータを浮かべる処理です。ループが終了したら、high と low の値を j に書き換えます。データが一度も交換されなかった場合、条件 low < high を満たさなくなるのでソートが終了します。あとはとくに難しいところはないでしょう。
それでは実行結果を示します。
表 : バブルソート改良版 (単位 : 秒) 個数: 乱数 : 昇順 : 逆順 : 山型 ----+-------+-------+-------+------- 1000: 0.077 : 0.000 : 0.093 : 0.061 2000: 0.306 : 0.000 : 0.394 : 0.323 4000: 1.281 : 0.000 : 1.504 : 1.257 8000: 4.572 : 0.001 : 6.130 : 4.654 表 : シェーカーソート版 (単位 : 秒) 個数: 乱数 : 昇順 : 逆順 : 山型 ----+-------+-------+-------+------- 1000: 0.087 : 0.000 : 0.112 : 0.055 2000: 0.257 : 0.000 : 0.423 : 0.268 4000: 1.019 : 0.000 : 1.738 : 0.982 8000: 3.882 : 0.001 : 6.961 : 3.995
バブルソートの改良により、昇順データは挿入ソートと同様に高速になりました。しかしながら、他のデータはほとんど変わりませんでした。シェーカーソートの場合、昇順データは挿入ソートと同様に高速になり、乱数データと山型データではバブルソートよりは少しですが高速になりました。シェーカーソートの効果は出ていると思いますが、遅いソートには変わりありません。なお、シェーカーソートは安定なソートです。
シェルソート (shell sort) は挿入ソートの改良版ともいえる方法です。最初は遠く離れた要素間でソートを開始し、徐々に間隔を狭めていきます。最後は隣り合った要素間でソートします。つまり、単純挿入ソートと同じになります。
間隔が大きいときは要素の個数が少ないので、単純なアルゴリズムでもソートにかかる時間は少なくてすみます。間隔が小さくなると要素の個数は多くなりますが、大まかにソートされているので挿入ソートでも高速にソートすることが可能です。
9 5 3 7 6 4 2 8 最初の状態
9 6 間隔を 4 で分割する
5 4
3 8
7 2
6 9 各群をソートする
4 5
3 8
2 7
6 3 9 8 間隔を 2 で分割する
4 2 5 7
3 6 8 9 各群をソートする
2 4 5 7
3 2 6 4 8 5 9 7 間隔を 1 で分割する（単純挿入ソートと同じ）
2 3 4 5 6 7 8 9 ソート完了
図 9 : シェルソート
プログラムは次のようになります。
リスト : シェルソート
def shell_sort0(buff):
k = len(buff)
gap = k // 2
while gap > 0:
for i in range(gap, k):
temp = buff[i]
j = i - gap
while j >= 0 and temp < buff[j]:
buff[j + gap] = buff[j]
j -= gap
buff[j + gap] = temp
gap //= 2
最初のループで間隔を徐々に狭めていきます。ここでは単純に 2 で割っていくことにしました。次のループで比較する要素を取り出します。最後のループでこの要素を挿入する位置を探索します。このときの探索は隣り合った要素ではなく gap 離れた要素を比較します。
2 番目のループでは、各群を並列にソートしていることに注意してください。群のひとつの要素を取り出して位置を決めたら、次の群の要素を取り出して位置を決めています。最後に gap は 1 になるので、挿入ソートと同じになりソートが完了します。
それでは実行結果を示します。
表 : シェルソート (単位 : 秒) 個数: 乱数 : 昇順 : 逆順 : 山型 ----+-------+-------+-------+------- 1000: 0.003 : 0.001 : 0.002 : 0.001 2000: 0.005 : 0.003 : 0.007 : 0.003 4000: 0.029 : 0.007 : 0.009 : 0.014 8000: 0.043 : 0.026 : 0.019 : 0.016
結果を見ればお分かりのように、シェルソートは速いですね。gap を常に奇数になるようにすると、シェルソートの実行速度はデータの個数 n の 1.5 乗に比例します。また、Knuth 先生によると、gap の値に次の数列を用いると、シェルソートは n の 1.25 乗に比例するそうです。
gap = ..., 121, 40, 13, 4, 1
この数列は 3 倍して 1 を加えることで得られる数列を逆にしたものです。これをプログラムすると、次のようになります。
リスト : シェルソートの改良版
def shell_sort(buff):
k = len(buff)
gap = 1
while gap < k // 9: gap = gap * 3 + 1
while gap > 0:
for i in range(gap, k):
temp = buff[i]
j = i - gap
while j >= 0 and temp < buff[j]:
buff[j + gap] = buff[j]
j -= gap
buff[j + gap] = temp
gap //= 3
それでは実行結果を示します。
表 : シェルソート改良版 (単位 : 秒) 個数: 乱数 : 昇順 : 逆順 : 山型 ----+-------+-------+-------+------- 1000: 0.002 : 0.001 : 0.001 : 0.001 2000: 0.005 : 0.002 : 0.003 : 0.003 4000: 0.015 : 0.009 : 0.014 : 0.009 8000: 0.033 : 0.008 : 0.024 : 0.013
少しですが速くなっていることがわかります。シェルソートは実装が簡単で、極端に要素数が大きくなければ十分実用になるソートです。なお、シェルソートは不安定なソートです。
コムソート (comb sort) はバブルソートの改良版といえる方法です。コームソートと呼ばれることもあります。今野氏の日記 (http://www.bsdclub.org/~motoyuki/d/d200005c.html#26-1) より引用します。
ソートの様子は間隔があいた櫛 (comb) ですいていくのに似ている。という感じである。 1.3 というのは数多くのデータを sort して実験的に得た数値とのこと。
- 最初に間隔が (要素数 / 1.3) の櫛で一度すく。
- 櫛の間隔を 1 / 1.3 しながら繰り返す。
- 櫛の間隔が 1 になったら bubble sort
出典は 『日経バイト 1991 年 11 月号』 とのことです。コムソートの考え方はシェルソートとよく似ています。シェルソートは挿入ソートの改良版といえる方法で、最初は遠く離れた要素間でソートを開始し、徐々に間隔を狭めていきます。そして、最後には隣り合った要素間でソートします。
シェルソートは実装が簡単で、要素数が極端に多くなければ十分実用になるソートですが、平均すればあとで説明するクイックソートよりも遅くなります。コムソートはシェルソートと同様の手法で改良を行っているようですが、それでどの程度の速さになるのかとても興味があります。
さっそくプログラムを作ってみましょう。次のリストを見てください。
リスト : コムソート
def comb_sort(buff):
k = len(buff)
gap = k
done = False
while gap > 1 or not done:
gap = (gap * 10) // 13
if gap == 0: gap = 1
elif gap == 9 or gap == 10: gap = 11
done = True
for i in range(k - gap):
if buff[i] > buff[i + gap]:
temp = buff[i]
buff[i] = buff[i + gap]
buff[i + gap] = temp
done = False
変数 gap の間隔でデータを比較していきます。データの順序が逆ならば交換するところはバブルソートと同じです。gap を 1 / 1.3 ずつ狭めていき、gap が 1 になったらバブルソートと同じになります。ここで、変数 done を終了判定のフラグとして使っていることに注意してください。ここがコムソートを理解するポイントです。
バブルソートの場合、データの交換が行われないときはソートが完了しています。つまり、done が True のままであれば、ソートを終了していいわけです。櫛をすくことでデータはおおまかにソートされるため、バブルソートの途中でソートが完了する可能性は極めて高くなるでしょう。これがコムソートの原理です。
それから、間隔 gap が 9, 10 の場合には強制的に 11 にすることで、速度が向上するように改良したコムソートを comb sort 11 というそうです。今回のプログラムは comb sort 11 を使っています。
それでは実行結果を示します。
表 : コムソート (単位 : 秒) 個数: 乱数 : 昇順 : 逆順 : 山型 ----+-------+-------+-------+------- 1000: 0.003 : 0.002 : 0.002 : 0.002 2000: 0.014 : 0.008 : 0.004 : 0.004 4000: 0.012 : 0.014 : 0.011 : 0.012 8000: 0.046 : 0.020 : 0.020 : 0.021
バブルソートやシェーカーソートと比べると、コムソートの方が断然速いですね。シェルソートと同程度の速度になりました。
次は高速なソートアルゴリズムとして有名なクイックソート (quick sort) を取り上げます。要素数を N とすると、クイックソートの平均的な実行時間は N * log N に比例しますが、最悪の場合は N の 2 乗に比例する遅いソートになってしまいます。クイックソートは拙作のページ「新・お気楽 Python プログラミング入門第 3 回」で取り上げましたが、ここでも簡単に説明しておきましょう。
クイックソートはある値を基準にして、要素をそれより大きいものと小さいものの 2 つに分割していくことでソートを行います。2 つに分けた各々の区間を同様に分割して 2 つの区間に分けます。最後は区間の要素がひとつになってソートが完了します。
9 5 3 7 6 4 2 8 最初の状態
9 5 3 7 6 4 2 8 7 を枢軸にして左側から 7 以上の値を探し、
L R 右側から 7 以下の値を探す。
2 5 3 7 6 4 9 8 交換する
L R
2 5 3 7 6 4 9 8 検索する
L R
2 5 3 4 6 7 9 8 交換する
L R
2 5 3 4 6 7 9 8 検索する。R と L が交差したら分割終了。
R L
[2 5 3 4 6] [7 9 8] この 2 つの区間について再び同様な分割を行う
図 10 : クイックソート
基準になる値のことを「枢軸 (pivot)」といいます。枢軸は要素の中から適当な値を選びます。今回は中央にある要素を選ぶことにしましょう。上図を見てください。左側から枢軸 7 以上の要素を探し、左側から 7 以下の要素を探します。探索のときは枢軸が番兵の役割を果たすので、ソート範囲外の要素を探索することはありません。見つけたらお互いの要素を交換します。探索位置が交差したら分割は終了です。
あとは同じ手順を分割した 2 つの区間に適用します。これは再帰定義を使えば簡単に実現できます。分割した区間の要素数が 1 になったときが再帰の停止条件になります。プログラムは次のようになります。
リスト : クイックソート (1)
def quick_sort(buff, low, high):
pivot = buff[(low + high) // 2]
i = low
j = high
while True:
while pivot > buff[i]: i += 1
while pivot < buff[j]: j -= 1
if i >= j: break
temp = buff[i]
buff[i] = buff[j]
buff[j] = temp
i += 1
j -= 1
if low < i - 1: quick_sort(buff, low, i - 1)
if high > j + 1: quick_sort(buff, j + 1, high)
def qsort(buff):
quick_sort(buff, 0, len(buff) - 1)
関数 quick_sort の引数 buff がソートするリスト、low が区間の下限値、high が区間の上限値です。quick_sort は buff の low から high までの区間をソートします。最初に、区間の中央にあるデータを枢軸として選びます。そして、最初の while ループで pivot を基準にして区間を 2 つに分けます。
次の while ループで、左側から枢軸以上の要素を探しています。ここでは枢軸以上という条件を、枢軸より小さい間は探索位置を進める、というように置き換えています。同様に次の while ループで右側から枢軸以下の要素を探します。お互いの探索位置 i, j が交差したら分割は終了です。break 文で while ループから脱出します。そうでなければお互いの要素を交換します。交換したあとは i と j の値を更新しておくことを忘れないでください。
そして、分割した区間に対して quick_sort を再帰呼び出しします。このとき要素数をチェックして、2 個以上ある場合に再帰呼び出しを行います。この停止条件を忘れると正常に動作しません。ご注意ください。
クイックソートは、枢軸の選び方で効率が大きく左右されます。区間の中間値を枢軸に選ぶと、区間をほぼ半分に分割することができます。この場合がいちばん効率が良く、データ数を N とすると N * log2 N に比例する時間でソートすることができます。
逆に、区間での最大値または最小値を枢軸に選ぶと、その要素と残りの要素の 2 つに分割にされることになります。これが最悪の場合で、分割のたびに最大値もしくは最小値を選ぶと、実行時間は N2 に比例することになります。つまり、挿入ソートと同じくらい遅いソートになるのです。それだけでなく、要素数が多くなるとスタックがオーバーフローする危険性もあります。
今回は区間の中央に位置する要素を枢軸としたので、中央付近に大きい要素があるデータが最悪の場合にあてはまります。つまり、山型データがこのプログラムでは最悪の結果になるのです。
それでは実行結果を示します。
表 : クイックソート (単位 : 秒) 個数: 乱数 : 昇順 : 逆順 : 山型 -----+-------+-------+-------+------- 1000: 0.002 : 0.001 : 0.001 : 0.016 2000: 0.004 : 0.001 : 0.002 : --- 4000: 0.006 : 0.004 : 0.007 : --- 8000: 0.029 : 0.010 : 0.008 : --- 16000: 0.039 : 0.014 : 0.023 : --- 32000: 0.068 : 0.030 : 0.031 : --- 64000: 0.142 : 0.071 : 0.079 : ---
山型データの --- は、スタックがオーバーフローしたことを示します。データ数が少ない場合、スタックオーバーフローは発生しませんが、実行時間はとても遅くなります。その他のデータでは、とても高速にソートすることができました。やっぱり、クイックソートは速いですね。なお、クイックソートは不安定なソートです。
それでは、クイックソートのプログラム (1) を改良してみましょう。まずは枢軸の選び方を工夫します。区間の中からいくつかの要素を選び、その中で真ん中の値を持つ要素を枢軸とします。たくさんの要素を選ぶとそれだけ最悪の枢軸を選ぶ危険性は減少しますが、真ん中の値を選ぶのに時間がかかってしまいます。そこで、実際には 3 つから 5 つの要素を選んで、その中で真ん中の値を持つ要素を枢軸とする場合が多いようです。
次に再帰呼び出しをループに展開します。2 つに分割した区間の長い方を自分で用意したスタックに積み、短い区間からソートしていきます。そうすると、スタックの深さは要素数を N とすると log 2 N 程度におさまります。たとえば、100 万個の要素をソートする場合でも、スタックの大きさは 20 程度あれば十分です。ひとつの区間の処理が終わったら、スタックから次の区間を取り出して処理を行います。これを図に示すと次のようになります。
スタック
[ A ][ B ] ( ) : 分割する。スタックは最初は空
(A) : A をスタックに積む
[ C ][D] (A) : B を分割する
[D] (C A) : C をスタックに積む
[ ] (C A) : D をソートする
[ C ][ ] (A) : C をスタックから取り出す
[ E ][F][ ] (A) : 分割する
[F][ ] (E A) : E をスタックに積む
[ ][ ] (E A) : F をソートする
[ E ] (A) : E をスタックより取り出す
・・・・・あとはスタックが空になるまで繰り返す・・・・・
図 11 : クイックソートでのスタックの動作
最後に、要素数が少なくなったらクイックソートを打ち切ります。そして、最後に挿入ソートで仕上げます。データ数が少ない場合は、クイックソートよりも単純なソートアルゴリズムの方が高速です。また、全体をソートする場合でも、すでに大まかにソートされているので、挿入ソートでも高速にソートすることができます。
まずは枢軸を選択する関数 select_pivot を作ります。
リスト : 枢軸の選択
def select_pivot(buff, low, high):
a = buff[low]
b = buff[(low + high) // 2]
c = buff[high]
if a > b:
tmp = a
a = b
b = tmp
if b > c:
b = c
if a > b: b = a
return b
区間 (low, high) から 3 つの要素を選びます。ここでは 先頭の位置 low、中央の位置 (low + high) // 2、最後尾の位置 high にある要素を選ぶことにしました。そして、a, b, c の中で真ん中の値を選んで返します。
ところで、枢軸の選択を工夫しても、その方法に対して最悪のデータが存在します。しかしながら、最悪の場合でも再帰呼び出しの削除とスタックの積み方の工夫により、エラーが発生することはありません。ただし、実行時間が遅くなるのは仕方がないところです。なお、参考文献『Ｃ言語による最新アルゴリズム事典』によると、枢軸を乱数で選ぶ方法もあります。興味のある方は試してみてください。
それでは、クイックソート本体を作ります。次のリストを見てください。
リスト : クイックソート (2)
LIMIT = 10
def quick_sort2(buff, low, high):
stack = []
while True:
if high - low <= LIMIT:
if len(stack) == 0: break
low, high = stack.pop()
else:
pivot = select_pivot(buff, low, high)
i = low
j = high
while True:
while pivot > buff[i]: i += 1
while pivot < buff[j]: j -= 1
if i >= j: break
temp = buff[i]
buff[i] = buff[j]
buff[j] = temp
i += 1
j -= 1
if i - low > high - j:
stack.append((low, i - 1))
low = j + 1
else:
stack.append((j + 1, high))
high = i - 1
insert_sort(buff)
def qsort2(buff):
quick_sort2(buff, 0, len(buff) - 1)
最初に、high - low の値をチェックします。LIMIT (10) 以下になったらクイックソートを打ち切ります。スタック stack にデータがなければ break で while ループを脱出して、最後に挿入ソート (insert_sort) で仕上げます。スタックには区間の上限値と下限値がタプルにまとめてセットされています。スタックにデータがある場合は、それを取り出して low と high にセットし、処理を繰り返します。
区間が LIMIT より大きい場合はクイックソートを行います。区間の分割は今までのプログラムと同じです。そして、長い方の区間をスタックにセットして、短い方の区間からクイックソートします。前半部分 (i - low) が長い場合は、(low, i - 1) をスタックに積んで (j + 1, high) をソートします。low の値を j + 1 に書き換えて処理を繰り返します。後半部分が長い場合は、(j + 1, high) をスタックに積んで (low, i - 1) をソートします。この場合は high を i - 1 に書き換えて処理を繰り返します。
それでは実行結果を示します。
表 : クイックソート改 (単位 : 秒) 個数: 乱数 : 昇順 : 逆順 : 山型 -----+-------+-------+-------+------- 1000: 0.002 : 0.001 : 0.001 : 0.002 2000: 0.003 : 0.002 : 0.002 : 0.007 4000: 0.012 : 0.003 : 0.004 : 0.018 8000: 0.019 : 0.011 : 0.009 : 0.032 16000: 0.036 : 0.014 : 0.014 : 0.056 32000: 0.070 : 0.030 : 0.038 : 0.117 64000: 0.131 : 0.062 : 0.072 : 0.266
このように、山型データでもエラーは発生しません。実行速度も非再帰版の方が少しだけ速くなります。
最後に 9 つの要素から枢軸を選ぶ方法を試してみましょう。この方法を median-of-9 と呼ぶようです。実際に 9 つの要素の中央値を求めているわけではありませんが、3 つの要素の中央値を求める方法 (median-of-3) よりも実行速度が速くなる場合があるようです。枢軸を選択するプログラムは次のようになります。
リスト : 枢軸の選択
# 中央値を返す
def median3(a, b, c):
if a > b:
if b > c:
return b
elif a < c:
return a
else:
return c
else:
if b < c:
return b
elif a < c:
return c
else:
return a
# 9 つの中から中央値を選ぶ
def median9(buff, low, high):
m2 = (high - low) // 2
m4 = m2 // 2
m8 = m4 // 2
a = buff[low]
b = buff[low + m8]
c = buff[low + m4]
d = buff[low + m2 - m8]
e = buff[low + m2]
f = buff[low + m2 + m8]
g = buff[high - m4]
h = buff[high - m8]
i = buff[high]
return median3(median3(a,b,c), median3(d,e,f), median3(g,h,i))
関数 median3() は引数 a, b, c の中で中央値となるものを返します。関数 median9() は区間 (low, high) から 9 つの要素を選びます。区間を (0, 1) とすると、0, 1/8, 1/4, 3/8, 1/2, 5/8, 3/4, 7/8, 1 の位置にある要素を選びます。
次に、9 つの要素を 3 つのグループ (0, 1/8, 1/4), (3/18, 1/2, 5/8), (3/4, 7/8, 1) に分けて、おのおののグループの中央値を median3() で求めます。さらに、その 3 つから中央値を median3() で求め、その値が枢軸となります。今回の方法は 9 つの要素の中央値を選択しているわけではありませんが、これでも十分に効果を発揮するようです。
あとは select_pivot() のかわりに median9() を呼び出すだけです。実行結果は次のようになりました。
表 : median-of-9 (単位 : 秒) 個数: 乱数 : 昇順 : 逆順 : 山型 -----+-------+-------+-------+------- 1000: 0.001 : 0.001 : 0.001 : 0.001 2000: 0.003 : 0.003 : 0.002 : 0.003 4000: 0.008 : 0.004 : 0.004 : 0.009 8000: 0.017 : 0.011 : 0.012 : 0.014 16000: 0.039 : 0.016 : 0.016 : 0.024 32000: 0.074 : 0.039 : 0.036 : 0.051 64000: 0.124 : 0.090 : 0.085 : 0.108
昇順と降順のデータでは median-of-9 のほうが少し遅くなりましたが、乱数データは median-of-9 のほうが少し速く、山型データでは 2 倍以上も速くなりました。median-of-9 は少ないコストで最悪のケースを回避する優れた方法だと思います。もちろん、median-of-9 でも最悪のケースが存在するはずですが、最悪のケースに遭遇する確率は median-of-3 よりも低くなると思います。興味のある方はいろいろ試してみてください。