クイックソート：Dev Basics／Keyword

クイックソートはピボット値を基準としてデータを分割し、分割後のデータに対して（ソートが完了するまで）同じ手法を適用していく高速なソートアルゴリズム。

» 2017年02月21日 05時00分公開

　クイックソートはデータを並べ替えるソート手法の1つで、何らかの値を基準としてそれより大きな値と小さな値に分け、分割されたそれぞれに対して、並べ替えが完了するまで同じ手法を適用していく。理想的な状況では、クイックソートは他のソート手法よりも高速に並べ替えを行える。

クイックソートのアルゴリズム

　クイックソートでは、「ピボット」と呼ばれる何らかの基準値を選定し、並べ替えの対象となるデータを、ピボット値よりも大きい（または以上）／小さい（または以下）値の集合に並べ替える（これを「パーティショニング」と呼ぶ）。そして、並べ替えられた2つのデータ群に対して、再度同じアルゴリズムを再帰的に適用していく。データが1個以下となった時点で、そのデータ群の並べ替えが完了する。

　以下に「1, 9, 3, 1, 5」の5つの要素からなる配列（リスト）に対してクイックソートを行っていく例を示す。なお、ここではピボットの値は配列（リスト）の中央の要素の値とする（要素数が偶数の場合は、「要素数／2－1」をインデックスとする要素の値とする）。なお、この図は次に示すPythonコードでソートを行った結果を簡略的に図化したものである（そのため、実際のソート処理では、2要素の配列／リストに対してピボット値を基準として分割処理を行った後、1要素の配列／リストについても再帰的な処理を行い、並べ替えの順序を確定させるなど、これよりも細かな単位で処理が行われている）。

クイックソートの例

　これを実際に行うPythonのコードを以下に示す（これはWikipediaの「クイックソート」の解説に含まれているC言語実装を基に、Pythonのコードとして書き直したもの）。

def qsort0(src, startpos, endpos):
if startpos >= endpos:
    return
pivotidx = (startpos + endpos) // 2
pivot = src[pivotidx]
#print('pivotidx: ', pivotidx, ' pivot value: ', pivot,
# ' search: src[', startpos, '] to src[', endpos, ']', sep='')
leftidx, rightidx = startpos, endpos
while True:
    while src[leftidx] < pivot:
      leftidx += 1
    while src[rightidx] > pivot:
      rightidx -= 1
    if leftidx >= rightidx:
      break
    src[leftidx], src[rightidx] = src[rightidx], src[leftidx]
    #print('swap src[', leftidx, '] = ', src[leftidx],
    # ' and src[', rightidx, '] = ', src[rightidx], sep='')
    #print(src)
    leftidx += 1
    rightidx -= 1
#print('src is divided to src[', startpos, '] - src[', leftidx-1, '] ',
# 'and src[', rightidx+1, '] - src[', endpos, ']', sep='')
qsort0(src, startpos, leftidx-1)
qsort0(src, rightidx+1, endpos)

クイックソートを行うPythonコードの例

　ここで定義している関数qsort0はリスト（Pythonでは配列はリストを用いて表現する）と、並べ替えの開始位置／終了位置をパラメーターに受け取り、受け取ったリストを破壊的に変更しながら、並べ替えを行うものだ。

　最初のif文は受け取ったリストが空であれば、その部分の並べ替えが完了しているものとして、それ以降の処理を行わないようにしている。その後、ピボット値を並べ替えを行う範囲の中央の要素としている。

　次のwhile文では、さらにwhile文をネストして、ピボット値と各要素を比較して、リスト内の要素をピボット値の左右に振り分けるような処理を行っている（これを「パーティショニング」と呼ぶ）。変数leftidxの値が変数rightidxの値以上になったら、並べ替え対象の範囲の捜査が全て完了したことになるので、外側のwhileループを終了する。最後にピボット値の左右の範囲を対象として再帰的に関数qsort0を呼び出している。

　組み込み関数printの呼び出しをコメントとして含めてあるので、並べ替えが実際にどのように行われていくかを見たければ、コメントアウトを外して、関数qsortを呼び出してみよう。

別の実装

　上で示した関数qsort0ではピボット値を境界として各要素を振り分けるために、リストの要素を破壊的に変更していたが、Pythonでは組み込み関数filterやリスト内包表記を用いて、よりスマートな形でパーティショニングを行える。これを行う実装を以下に示す（組み込み関数filterとラムダ式を組み合わせた場合のコードはコメントアウトして含めてある。どちらを使うのが高速かを試してみてほしい）。こちらの関数は元のリストを破壊せずに、新しくリストを作成して、それを呼び出し元に返すようになっている。

def qsort1(src):
if not src:
return []
pivot = src[0]
src = src[1:]
smaller = [x for x in src if x <= pivot]
bigger = [x for x in src if x > pivot]
#smaller = list(filter(lambda x: x <= pivot, src))
#bigger = list(filter(lambda x: x > pivot, src))
return qsort1(smaller) + [pivot] + qsort1(bigger)

リスト内包表記や組み込み関数filter／ラムダ式を利用してクイックソートを行う関数qsort1

　ここではピボット値をリストの先頭要素とし、リスト内包表記／組み込み関数filterで処理を行う対象をリストの2番目以降の要素とすることで、記述をシンプルなものにしている（関数qsort0のように、リストの中央の要素をピボット値として採用すると、「ピボット値より小さな値を要素とするリスト」「ピボット値と同じ値を要素とするリスト」「ピボット値よりも大きな値を要素とするリスト」の3つのリストを生成することになる。興味のある方は実際にどんなコードになるか考えてみよう）。

実行速度とその計測

　クイックソートは、一般に「最も高速なソートアルゴリズムである」といわれているが、これはピボット値を基準としたパーティショニングで、元のデータがほぼ均等に分割されるような場合である。これに対して、データが「1個：残りのデータ」のように分割されてしまう場合には、クイックソートは低速な処理となる。

　よって、分割がなるべく均等となるようにピボット値を選択することが、クイックソートにおいては重要になる。本稿で見たサンプルコードでは、リストの中央の要素の値や先頭要素の値を（無分別に）ピボット値として選択していたが、実際には「データの中から3つの要素を取り出して、その中央値（3つの値の中で真ん中の値）をピボットとする」などの工夫が必要となる。

　最後に本稿で見た2つの関数qsort0／qsort1とPythonに組み込みのlist.sortメソッド、Pythonで実装した（もともとが低速といわれている）バブルソート関数の実行速度を計測してみよう。まず、バブルソートを行う関数bubblesortのリストを以下に示す。高速化のための工夫は何もしていない。

def bubblesort(src):
while True:
    ordered = True
    for i in range(len(src)-1): # リスト全体を走査して、ある要素が右隣の要素
      if src[i] > src[i+1]:      # よりも大きければ、それらを入れ替える（だけ）
        src[i], src[i+1] = src[i+1], src[i]
        ordered = False
    if ordered: # 入れ替えが一度も行われなければ、全ての要素が昇順に並んでいる
      break

バブルソートを行う関数bubblesort

　また、実行時間の計測にはPythonのtimeitモジュールを使用する。timeitモジュールにはtimeit関数があり、これを以下のようにして使用する。

from timeit import timeit

timeit('実行する処理', globals=処理を実行する名前空間の指定, number=実行回数)

timeitモジュールのtimeit関数

　ここではglobals引数には「globals()」の結果を、number引数には100を渡す（100回実行し、その総実行時間を計測する）。また、処理対象のリストは要素数1000個で、その値は0～999の値の乱数値とする。よって、以下のコードをPythonの対話環境で実行していく。

from qsort import qsort0, qsort1, bubblesort
from random import randint
from timeit import timeit

number = 100
timeit('qsort0([randint(0, 1000) for x in range(1000)], 0, 999)',
       globals=globals(), number=number)
timeit('qsort1([randint(0, 1000) for x in range(1000)])',
       globals=globals(), number=number)
timeit('bubblesort([randint(0, 1000) for x in range(1000)])',
       globals=globals(), number=number)
timeit('[randint(0, 1000) for x in range(1000)].sort()',
       globals=globals(), number=number)

qsort0／qsort1／bubblesortの各関数とlist.sortメソッドの処理時間の計測

　これを実行した結果を以下に示す。

>>> from qsort import qsort0, qsort1, bubblesort
>>> from random import randint
>>> from timeit import timeit
>>>
>>> number = 100
>>> timeit('qsort0([randint(0, 1000) for x in range(1000)], 0, 999)',
...        globals=globals(), number=number)
0.5510283079997862
>>> timeit('qsort1([randint(0, 1000) for x in range(1000)])',
...        globals=globals(), number=number)
0.5992787139998654
>>> timeit('bubblesort([randint(0, 1000) for x in range(1000)])',
...        globals=globals(), number=number)
23.203046764999726
>>> timeit('[randint(0, 1000) for x in range(1000)].sort()',
...        globals=globals(), number=number)
0.24888211999996201

実行結果

　実際には1000個の要素を持つリストを毎回生成しているので、そのオーバーヘッドを考慮する必要もあるが、関数qsort0／qsort1はおおよそ似たような速度に（何度か繰り返していると、関数qsort1の方が関数qsort0よりも若干遅い傾向が見られた）、バブルソートは圧倒的に低速で、list.sortメソッドが最も高速という結果になった。とはいえ、バブルソートと比べれば、手書きで作成したクイックソートであってもそれなりに高速にデータを並べ替えられることが分かるはずだ（ではあるが、高速な手法があるのであれば、自作する必要はないだろう）。

　クイックソートは処理対象のデータを、ピボット値を基準として、それより大きな値からなるデータ群とそれより小さな値からなるデータ群に分割を行い、そのそれぞれに対して、並べ替えが完了するまで同じ手法を適用していく。理想的な状況では、クイックソートは他のソート手法よりも高速に並べ替えを行えるが、そのためには適切なピボット値を選択するなどの工夫を行った方がよい。