クイックソート

クイックソート (quicksort) もまた再帰的なソートアルゴリズムです。Tony Hoare (トニー・ホーア) によって 1959 年に発見され、1961 年に発表されました。このアルゴリズムの各ステップを次に示します。クイックソートにおいて本当の作業と呼べるのは再帰呼び出しの前に配列を小配列に振り分ける部分であり、この振り分けによって最後のマージ処理が必要なくなります。

配列からピボット (pivot) を選ぶ。
配列を三つの小配列に分ける。三つの配列にはそれぞれピボットよりも小さい要素、ピボットと等しい要素、ピボットよりも大きい要素を入れる。
一番目と三番目の小配列を再帰的にクイックソートする。

\[ \begin{array}{rc} \text{\small 入力}: & \texttt{ S O R T I N G E X A M P L} \\ \text{\small ピボットの選択}: & \texttt{ S O R T I N G E X A M }{\color{#B52F1B}{\texttt{P}}}\texttt{ L} \\ \text{\small 分割}: & \texttt{ A G O E I N L M }{\color{#B52F1B}{\texttt{P}}}\texttt{ T X S R} \\ \text{\small 左の再帰}: & \texttt{ A E G I L M N O }{\color{#B52F1B}{\texttt{P}}}\texttt{ T X S R} \\ \text{\small 右の再帰}: & \texttt{ A E G I L M N O }{\color{#B52F1B}{\texttt{P}}}\texttt{ R S T X} \end{array} \]

図 1.7

クイックソートの例

クイックソートの詳細な手順を次の疑似コードに示します。\(\textsc{Partition}\) サブルーチンの入力 \(p\) はソートされてない配列におけるピボット要素の添え字であり、出力はピボットの新しい添え字です。効率良く配列を分割するアルゴリズムはいくつか知られていますが、ここに示したのは Nico Lomuto によるものです¹。変数 \(l\) がピボットよりも小さい要素の数を保持します。

procedure \(\texttt{QuickSort}\)(\(A[1..n]\))

if \( n > 1 \) then

ピボット \(A[p]\) を選ぶ

\( r \leftarrow \)\(\texttt{Partition}\)(\(A, p\))

\(\texttt{QuickSort}\)(\( A[1..r-1 \)]) \(\quad\) ⟨⟨再帰！⟩⟩

\(\texttt{QuickSort}\)(\( A[r+1..n \)]) \(\quad\) ⟨⟨再帰！⟩⟩

procedure \(\texttt{Partition}\)(\(A[1..n], p\))

swap \( A[p] \leftrightarrow A[n] \)

⟨⟨\(l = \) ピボット未満の要素の数⟩⟩

\( l \leftarrow 0 \)

for \( i \leftarrow 1 \) to \( n - 1 \) do

if \( A[i] < A[n] \) then

\(l \leftarrow l + 1\)

swap \( A[l] \leftrightarrow A[i] \)

swap \( A[n] \leftrightarrow A[l + 1] \)

return \( l + 1 \)

図 1.8

クイックソート

正しさ

マージソートと同じように、\(\textsc{QuickSort}\) の正しさの証明には帰納法を二回使います。最初に \(\textsc{Partition}\) が正しく配列を分割することを示し、次に \(\textsc{Partition}\) が正しいという仮定の下で \(\textsc{QuickSort}\) が正しいことを示します。 \(\textsc{Partition}\) の正しさの証明では次のループ不変条件を示す必要があります: 「メインループの各反復の終端において、小配列 \(A[1..l]\) の要素は \(A[n]\) よりも小さく、また小配列 \(A[l+1..i]\) の要素は \(A[n]\) よりも小さくない」簡単なものの面倒なこの証明の詳細は読者への練習問題とします。

解析

クイックソートの解析はマージソートのものと似ています。\(\textsc{Partition}\) は決まった処理を要素ごとに行う for ループなので、実行時間は \(O(n)\) です。一方 \(\textsc{QuickSort}\) の実行時間 \(T(n)\) についての再帰的関係はソートした配列におけるピボット要素の順位 \(r\) に依存します: \[ T(n) = T(r - 1) + T(n - r) + O(n) \]

もしなんらかのマジカルな方法で配列の \(A\) の中央値をピボットとして選択できるなら \(r = \lceil n/2 \rceil\) となります。このとき二つの小問題のサイズは可能な範囲で最も近くなり、再帰方程式は次のようになります: \[ T(n) = T(\lceil n/2 \rceil - 1) + T(\lceil n/2 \rceil) + O(n) \leq 2T(n/2) + O(n) \] 再帰木の方法、あるいは「あ、この再帰方程式ってマージソートで解いたじゃん」によって \(T(n) = O(n \log n)\) が分かります。

この章でこれから見ることですが、ソートされる前の配列から中央値を選択する処理は実際に線形時間で行えます。しかしアルゴリズムは複雑であり、\(O(\cdot)\) という表記に隠されている定数部分が大きすぎるので、このアルゴリズムを使ってソートを実装すると実用できる速さになりません。そのため多くのプログラマーはもっと単純な、例えば配列の最初または最後を選択するといった方法でピボットを選んでいます。この場合 \(r\) は \(1\) から \(n\) の任意の値を取るので、再帰方程式は次のようになります: \[ T(n) = \max_{1 \leq r \leq n} (T(r - 1) + T(n - r) + O(n)) \] 最悪の場合 ―― \(r = 1\) または \(r = n\) ―― では、二つの小問題の大きさが大きく異なることになり、\(T(n) \leq T(n - 1) + O(n)\) となります。この場合の解は \(\pmb{T(n) = O(n^{2})}\) です。

ピボットの選択に使われるもう一つのヒューリスティックは "三つの中央値" と呼ばれるものです。これは配列から要素を三つ (よくあるのは配列の最初、中央、最後から) 取り、その中央値をピボットとして採用するという方法です。ピボットを決め打ちで採用するものと比べた場合、この方法を使うと実際の実行速度がいくらか向上します。特に配列が最初から (ほぼ) ソートされている場合では速度の向上が顕著です。しかし最悪の場合では \(r = 2\) または \(r = n - 1\) となるので、"三つの中央値" ヒューリスティックを使った場合の再帰方程式は \(T(n) \leq T(1) + T(n - 2) + O(n)\) であり、この解は \(T(n) = O(n^{2})\) のままです。

ピボット要素が "平均して" 配列の中央部分、例えば上から \(n/10\) と \(9n/10\) の間に収まるはずだというのは直感的に分かります。この直感を信じれば、このアルゴリズムの平均実行時間は \(O(n \log n)\) となります。確かにこの直感を定式化することもできますが、最もよく使われる定式化では、入力データの任意の置換が全て同じ頻度で入力されるという、全く現実的でない仮定が置かれます。現実のデータはランダムかもしれませんが、事前にランダムであることが分かるという意味のランダムではありませんし、一様乱数では決してありません²！

どういうわけか "最良" 実行時間なるものを考える人もいますが、私たちはしません。

Hoare が提案したのはもっと複雑な "双方向" 分割アルゴリズムです。Lomuto のアルゴリズムと比べるとこのアルゴリズムには実用上の利点がある一方で、off-by-one エラーが無限ループを引き起こします。^[return]
一方で、ピボットの添え字 \(p\) を一様な乱数によって選んだ場合、\(\textsc{QuickSort}\) は全ての入力に対して高い確率で \(O(n \log n)\) となります。ここで鍵となるのは乱数がアルゴリズムによって制御されており、コードを読んでから入力を作成する悪意に満ちた全能の攻撃者は制御できない点です。乱数クイックソートの解析は残念ながらこの本の範囲を超えますが、関連する講義ノートを http://algorithms.wtf/ から入手できます。^[return]