クイックソート

クイックソートは最もよく使われるソートアルゴリズムの1つです。ピボットを選び、リストをピボットより小さい値と残りに分け、両側を同じ方法で並べ替えます。実際に高速で、追加のリストも不要ですが、速さはピボット次第です。

ピボットの棒を中心に分割された棒:小さい棒が片側、大きい棒が反対側にあり、ピボットはその間にある
ピボットの棒を中心に分割された棒:小さい棒が片側、大きい棒が反対側にあり、ピボットはその間にある

考え方

値を1つ選んでピボットにします。ピボットより小さい値がすべてその前に、それ以外の値が後ろに来るようにリストを並べ替えます。この並べ替えを分割(パーティション)と呼び、ピボットは整列後のリストで本来あるべき位置にちょうど収まります。両側は独立した問題になるので、それぞれをクイックソートで並べ替えます。値が1つ以下の側はすでに整列済みです。

分割の手順

このアプリは Lomuto の分割を使います。ピボットは部分の末尾に移されます。目印は先頭から始まり、その前にある値はすべてピボットより小さい値です。ほかの各値をピボットと比較し、小さければ目印の位置に交換して、目印を1つ進めます。最後に、ピボットを目印の位置に交換します。5, 1, 4, 2, 8 で最後の値をピボットにすると、4つの値はすべて8より小さいので、8は末尾に残ります。部分 5, 1, 4, 2 は2を中心に分割されて 1, 2, 4, 5 になり、4, 5 は5を中心に分割されます。比較8回、交換2回、分割3回です。

良いピボットと悪いピボット

どのピボットも真ん中に来れば、分割のたびに問題が半分になり、比較は約 n log₂ n 回で済みます。ランダムなリストではピボットが完璧なことはまれですが、たいてい十分に良く、ランダムな40個の値ではアプリは約190回の比較を数えます。最悪の場合は、ピボットが常に最小値か最大値のときです。最後の値をピボットにすると、整列済みや逆順のリストがまさにそうなります。各分割でピボットしか取り除けず、比較は n(n − 1)/2 回、40個なら780回です。

ピボットの選び方

ランダムなピボットは特定の順序でだますことができないので、どんな入力でも最悪の場合はきわめて起こりにくくなります。3値の中央値、つまり最初・中央・最後の要素の中央値は計算が安く、整列済みや逆順のリストにもうまく対応します。アプリで整列済みのリストに両方を試すと、比較回数は780回から約150回に減ります。等しい値が多い場合は別の問題で、それらはすべてピボットの片側に集まります。ピボットと等しい値を中央の部分にまとめる3分割(three-way partition)で解決できます。

歴史と用途

Tony Hoare は1959年にクイックソートを考案し、1961年に発表しました。彼自身の分割は両端から走査し、交換回数が少なくなります。ここで示す、より単純な Lomuto 版は教科書を通じて広まりました。クイックソートはその場で並べ替え、内側のループがとても短いため、実際にはマージソートより速いことが多いですが、安定ではありません。C++ 標準ライブラリのソートに使われる introsort は、クイックソートを実行し、分割が偏りすぎるとヒープソートに切り替えるので、最悪の場合も n log n に保たれます。

トニー・ホーア。1959年にクイックソートを考案し、1961年に発表した。
トニー・ホーア。1959年にクイックソートを考案し、1961年に発表した。

試してみよう

アプリを開いて「ステップ」を押してください。分割中の部分には網掛けがかかり、ピボットは専用の色で表示され、破線は左側の部分(ピボットより小さい値)の終わりを示します。各ピボットは最終位置に着くと緑色になります。整列済みのリストと最後の値のピボットを選んでから3値の中央値に切り替え、カウンターを比べてみましょう。

よくある質問

クイックソートの時間計算量は?

平均およびピボットが良い場合は O(n log n)、最悪の場合は O(n²) です。その場で並べ替えます。小さい側を先に並べ替えれば、再帰に必要な追加メモリは O(log n) です。

Lomuto と Hoare の分割の違いは?

Lomuto は目印を1つ使って左から右へ走査します。わかりやすく、このアプリで示しているのもこの方法です。Hoare は両端から互いに向かって走査し、間違った側にある値のペアを交換します。平均すると交換回数は約3分の1になります。

等しい値が多いとクイックソートが遅くなるのはなぜですか?

ピボットと等しい値はすべて同じ側に行くので、異なる値が少ないリストは偏って分かれ、すべて等しい値のリストは最悪の場合と同じくらい遅くなります。ピボットと等しい値を中央に集める3分割で、これを避けられます。

クイックソートは安定ですか?

いいえ。分割中の交換で値が遠くまで移動するため、等しい値の順序が変わることがあります。

試してみますか?

ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。

クイックソートを試す