Design-and-analysis-of-algorithms-quick-sort

DAA-クイックソート

分割統治の原理で使用されます。 クイックソートは、実装するのが難しくないため、多くの状況で選択されるアルゴリズムです。 これは適切な汎用ソートであり、実行中に比較的少ないリソースを消費します。

利点

• 小さな補助スタックのみを使用するため、インプレースです。
• n 個のアイテムをソートするには、 _ n（log n）_ 時間だけが必要です。
• 非常に短い内部ループがあります。
• このアルゴリズムは徹底的な数学的分析を受けており、パフォーマンスの問題について非常に正確な声明を出すことができます。

デメリット

• 再帰的です。 特に、再帰が利用できない場合、実装は非常に複雑です。
• 最悪の場合、2次（つまりn2）時間を必要とします。
• 壊れやすい、つまり 実装の単純な間違いは、気付かれずにパフォーマンスが低下する可能性があります。

クイックソートは、特定の配列 A [p …​ r] _ 2つの空でないサブ配列 _A [p …​ q] _' および _A [q + 1 …​ r] _ * A [p …​のすべてのキー q] _ は、 ' A [q + 1 …​のすべてのキー以下です r] _ 。

次に、2つのサブ配列は、クイックソートの再帰呼び出しによってソートされます。 パーティションの正確な位置は、指定された配列に依存し、インデックス q はパーティション化手順の一部として計算されます。

Algorithm: Quick-Sort (A, p, r)
if p < r then
   q Partition (A, p, r)
   Quick-Sort (A, p, q)
   Quick-Sort (A, q + r, r)

配列全体をソートするには、最初の呼び出しが Quick-Sort（A、1、length [A]） であることに注意してください。

最初のステップとして、クイックソートは、ピボットとしてソートされる配列内のアイテムの1つを選択します。 次に、配列はピボットの両側で分割されます。 ピボット以下の要素は左に移動し、ピボット以上の要素は右に移動します。

アレイの分割

分割手順は、サブアレイをその場で再配置します。

Function: Partition (A, p, r)
x ← A[p]
i ← p-1
j ← r+1
while TRUE do
   Repeat j ← j - 1
   until A[j] ≤ x
   Repeat i← i+1
   until A[i] ≥ x
   if i < j then
      exchange A[i] ↔ A[j]
   else
      return j

分析

Quick-Sortアルゴリズムの最悪の複雑さは O（n ^ 2 ^） です。 ただし、この手法を使用すると、一般的には O（n log n） 時間で出力が得られます。