ソートアルゴリズム：クイックソート（Quicksort）解説

no_mkd

一.クイックソートアルゴリズムの利点、なぜ「クイック」ソートと呼ばれるのか？

Quicksort はマージソートアルゴリズムの最適化で、マージソートの利点を継承し、同様に分割統治思想を応用しています。

いわゆる分割統治思想とはある問題に対して「分けて統治する」ことで、分割統治思想で問題を解決するには 2 つのステップが必要です：

1. どのように「分ける」か？（どのように問題の規模を縮小するか）
2. どのように「統治する」か？（どのように子問題を解決するか）

クイックソートの前身はマージですが、マージには無視できない欠点があったため、クイックソートが生まれました。マージの最大の問題は追加の記憶領域が必要であり、かつマージプロセスが不確定であるため、各要素のシーケンス内の最終位置が予測不可能なことです。この点に対して、クイックソートは新しい思路を提案しました：より多くの時間を「分ける」ことに使い、より少ない時間を「統治する」ことに使う。これにより追加の記憶領域の問題を解決し、アルゴリズム効率を向上させました。

クイックソートが「クイック」ソートと呼ばれる理由は、平均時間において最も速いからです。主な理由はハードウェア面であり、各ラウンドのクイックソートでは「ピボット」（つまり境界点としての値）を指定する必要があり、1 ラウンドで関わるすべての比較はこの「ピボット」と比較されます。そのため、この「ピボット」をレジスタに置くことができ、こうすれば効率は自然に大幅に向上します。これに加えて、クイックソートの高効率さは分割統治思想とも切り離せません。

二.アルゴリズム思想

クイックソートの思想に従えば、既知のシーケンスをソートするには以下のステップがあります：

1. 「ピボット」を指定

   注意、「指定」であり、明確な制約条件はありません。つまり、このピボットは任意の要素で、一般的には 2 種類のピボットを選択します：現在のシーケンスの先頭要素、またはランダムに選択

   2 つの方法にはそれぞれ長所と短所があります。前者は簡単ですが、アルゴリズム効率に影響を与える可能性があります

   クイックソートでは、ピボットの最終位置が中間位置に近ければ近いほど効率が良くなります。読み方は少し奇妙に感じるかもしれませんが、ピボットは値（具体的な要素）であり、文字通りの意味の位置ではないことに注意してください。ピボットが最終シーケンス内の位置が前または後ろにある場合、アルゴリズム効率は高くありません（「最悪の場合」に似ています）

   したがって、後者はある程度最悪の場合の発生回数を減らしますが、ランダム選択には追加の時間が必要です

   そのため、具体的な応用では一般的に 1 番目の方法で「ピボット」を指定します。つまり、現在のシーケンスの先頭要素を直接「ピボット」とします

2. 1 ラウンドのクイックソートを実行

   クイックソートでは、1 ラウンドの操作の最終目的は「ピボット」を它が行くべき場所に置くことです。例を挙げると、既知のシーケンス{7, -1, 5, 23, 100, 101}の場合、1 ラウンド目のクイックソートの結果は{_, _, 7, _, _, _}となります

   先頭要素（ピボット）が它が行くべき場所に行ったことがわかります（最終結果シーケンスでは、7 はまさに中間位置にあります、そうですよね）

3. 子シーケンスに対してクイックソートを実行

   第 2 歩は 7 の最終位置を確定しただけでなく、元のシーケンスを自然に 2 つの子シーケンス{_, _}と{_, _, _}に分割しました。ここでは「_」で具体的な数値を置き換えています。第 2 歩の結果が具体的に何なのかは、実際に 1 ラウンドのクイックソートを実行しない限りわからないからです。もちろん、ここでは必要ありません。下に具体的な例に対する詳しい説明があります

   自然に子シーケンスに対して同じ操作を実行し、その後子シーケンスの子シーケンスに対して同じ操作を実行する...再帰

   すべての子シーケンスの長さが 1 になったとき、ソート終了

三.具体的な例

現在シーケンス{9, 0, 8, 10, -5, 2, 13, 7}があります。クイックソートアルゴリズムでソートします

まず、いくつかの特殊な記号を宣言して、説明しやすくします

• 数字の後ろに付く大文字はポインタを表します。例えば 2.5P はポインタ P が要素 2.5 の位置を指していることを表します
• @はゴミ数字を表します。つまり、現在の位置が何であっても構いません。後で詳しい説明があります
• _はその位置の要素が 1 行前と同じであることを表します（_は不変を表します）

P.S.本当に理解したい場合は、今すぐ紙とペンを用意してください。目だけで見るのは絶対に不十分です

以下、正式�� 1 ラウンドのクイックソートプロセスの解析を始めます

説明：

1. 1 行目は初期状態です。クイックソートには 2 つのポインタ L と H（低位 Low、高位 High を表します）、1 つの一時変数 temp が必要です

   初期時、低位ポインタ L は先頭要素 9 を指し、高位ポインタ H は末尾要素 7 を指し、temp= 先頭要素 9（temp がいわゆる「ピボット」です）

2. 以下の操作を実行：（なぜかは後で説明）

   *H と temp を比較*し、*H が大きい場合、H を前に移動して比較を継続。*H が小さい場合、*L = *H、*H = @（H が指す値がゴミ数字になる）、L を後に移動

   7 < 9 なので、L が指す 9 を 7 に変え、H が指す 7 をゴミ数字に変え、L ポインタを後に移動して、2 行目の結果を得ます

3. 以下の操作を実行：（なぜかは後で説明）

   *L と temp を比較*し、*L が小さい場合、L を後に移動して比較を継続。*L が大きい場合、*H = *L、*L = @（L が指す値がゴミ数字になる）、H を前に移動

   0 < 9 なので、L を後に移動して、3 行目の結果を得ます

4. 8 < 9 なので、同上
5. 10 > 9 なので、H が指すゴミ数字@を 10 に変え、L が指す 10 をゴミ数字に変え、H ポインタを前に移動して、5 行目の結果を得ます
6. 13 > 9 なので、H ポインタを前に移動して、6 行目の結果を得ます
7. 2 < 9 なので、L が指すゴミ数字@を 2 に変え、H が指す 2 をゴミ数字に変え、L ポインタを後に移動して、7 行目の結果を得ます
8. -5 < 9 なので、L ポインタを後に移動して 8 行目の結果を得ます
9. 以下の操作を実行：（なぜかは後で説明）

   L = H の場合、*L = *H = temp、1 ラウンドのクイックソート終了

   L ポインタと H ポインタが重なったので、L が指すゴミ数字@を temp の値 9 に変え、1 ラウンド終了

   これで、ピボット 9 の最終位置を確定しました。与えられたシーケンスも自然に 2 つの子シーケンス{7, 0, 8, 2, -5}と{13, 10}に分割されました。子シーケンスに対して同じ操作を実行し、最終的に整列されたシーケンスを得ることができます

次に、上で言及した 3 組の操作を説明します

簡単に言えば、上の 3 組の操作は temp の最終位置を見つけるためのものです。各ステップで L の前がすべて temp より小さく、H の後ろがすべて temp より大きくなることを保証します。したがって、H と L が重なる位置の要素は temp の値になるしかありません

上で言及した 3 組の操作は以下のいくつかのルールに簡略化できます。記憶しやすくなります：

1. L が指す値が小さい場合は L を移動、そうでなければ値を代入してポインタを移動
2. H が指す値が大きい場合は H を移動、そうでなければ同上
3. HL が重なった場合、temp を代入
4. H、L は交互に temp と比較。ルールは 1 回代入した後 1 ラウンド終了（したがって最初は L と temp の比較から始めても構いません。次のラウンドは H と temp を比較、さらに次のラウンドは...）

P.S.どのように移動するかについては、低位ポインタは高位にのみ移動でき、逆も同様です。値を代入した後にどのポインタを移動するかについては、もちろんもう一方のポインタ（現在のポインタではない）です

四.まとめ

ソートアルゴリズムの応用は具体的な環境に合わせて考慮する必要があります。例えば、与えられたシーケンスが部分的に整列されている場合、当然バイナリ挿入アルゴリズムが最も速くなります...

クイックソートも最善というわけではありません。その「速さ」は総合的な考慮に基づいて構築されたもので、具体的な状況では必ずしもそうとは限りません

クイックソートも万能ではありません。例えば、与えられたシーケンスの規模が小さい場合、選択ソートの方がクイックソートよりもはるかに優れています

また、一般的なソートアルゴリズムには以下があります：

1. バケットソート/ビンソート（Bucketsort）
2. 基数ソート（Radixsort）
3. 挿入ソート（Insertsort）
4. 選択ソート（Selectsort）
5. マージソート（Mergesort）
6. クイックソート（Quicksort）
7. ヒープソート（Heapsort）