ベストアンサー
ピボットの検索、現在の配列の分割、再実行など、クイックソートの仕組みについて十分な知識があるため各サブ配列で同じように再帰的に、次のことを考慮して時間計算量を分析するのは簡単です：
最悪の場合：
最悪の場合は、各再帰で、分割配列への次のピボットが配列の最後にあるときに発生します。
Nの場合は配列の長さであり、配列の開始位置に現在のピボットがあります。
最後のインデックスのピボットは、配列を最初から最後までトラバースする場合にのみ識別されます。ピボットを修正し、結果の長さのサブ配列を分割すると、（N-1）、1 になります。
この（N-1）サブ配列は、最後のインデックスで次のピボットを検出し、長さが（N-2）、1 。
このプロセスは、最終的なサブ配列の長さが両方とも 1,1 になるまで繰り返されます。
つまり、これは
ステップ1で数学的に紙に描くことができます： N 要素を使用すると、このパーティションの時間計算量は
T（N）= N + T（N-1）
ここで、T（N-1）はパーティションの時間計算量です。再帰的に処理され、NはN個の要素を固定ピボットと比較するために必要な時間です。
ステップ2： N-1 要素、
T（N-1）=（N-1）+ T（N-2）
T（N-2）=（N-2）+ T（N-3）
…
T（3）= 3 + T（2）
T（2）= 2 + T（1）
T（ 1）= 0長さ「1」の配列をパーティション分割する時間は0でパーティションなし
したがって、
T（N）= N +（N-1）+（N-2）… + 3 +2≈N*（N + 1） / 2
=（N ^ 2）/ 2
= O（N ^ 2）
平均的なケース：
平均的な場合、次のピボットは、比較することにより、配列を2つの等しい長さに分割します（N / 2）時間の複雑さをもたらすすべての要素 N。
T（N）= 2 * T（N / 2）+ N
両側をNで除算
T（N）/ N = 2 *（T（N / 2）/ N）+ N / N
T（N）/ N = 2 *（T （N / 2）/ N）+ 1
したがって、T（N）/ N =（T（N / 2）/（N / 2））+ 1
T（N / 2） /（N / 2）= T（N / 4）/（N / 4）+ 1
…
T（2）/ 2 = T（1）/ 1 + 1
As T（1）= 0
T（2）/ 2 = 1
T（4）/ 4 = T（2）+ T （1）
T（8）/ 8 = T（4）+ T（2）+ T（1）## log（n）項
したがってT（N） / N = log N
T（N）= NlogN
回答
QuickSortは分割統治アルゴリズムです。要素をピボットとして選択し、選択したピボットの周りに指定された配列を分割します。さまざまな方法でピボットを選択するquickSortにはさまざまなバージョンがあります。
- 常に最初の要素をピボットとして選択します。
- 常に最後の要素をピボットとして選択します（実装済み）以下）
- ピボットとしてランダムな要素を選択します。
- ピボットとして中央値を選択します。
クイックソートの重要なプロセスはパーティションです（ ）。パーティションのターゲットは、配列と配列の要素xをピボットとして指定し、xを並べ替えられた配列の正しい位置に配置し、すべての小さい要素（xより小さい）をxの前に配置し、すべての大きい要素（より大きい）を配置します。 xより）xの後。これはすべて線形時間で実行する必要があります。
クイックソートの手順は次のとおりです。
Step 1 − Choose the highest index value has a pivot
Step 2 − Take two variables to point left and right of the list excluding pivot
Step 3 − left points to the low index
Step 4 − right points to the high
Step 5 − while value at left is less than pivot move right
Step 6 − while value at the right is greater than pivot move left
Step 7 − if both step 5 and step 6 does not match swap left and right
Step 8 − if left ≥ right, the point where they met is the new pivot
クイックソートの実装：
Quicksort(A,p,r) {
if (p < r) {
q <- Partition(A,p,r)
Quicksort(A,p,q)
Quicksort(A,q+1,r)
}
}
Partition(A,p,r)
x <- A[p]
i <- p-1
j <- r+1
while (True) {
repeat
j <- j-1
until (A[j] <= x)
i <- i+1
until (A[i] >= x)
if (i A[j]
else
return(j)
}
}
クイックソートの時間計算量：
最悪ケース： 最悪のケースは、パーティションプロセスが常に最大または最小の要素をピボットとして選択する場合に発生します。最後の要素が常にピボットとして選択される上記のパーティション戦略を検討すると、配列がすでに昇順または降順で並べ替えられている場合に最悪のケースが発生します。以下は、最悪の場合の再発です。
T(n) = T(0) + T(n-1) + (n)
which is equivalent to
T(n) = T(n-1) + (n)
上記の繰り返しの複雑さは n square
ベストケース： ベストケースは、パーティションプロセスが常に選択する場合に発生しますピボットとしての中央の要素。以下は、最良の場合の繰り返しです。
T(n) = 2T(n/2) + (n)
上記の繰り返しの複雑さは nLogn
平均的なケース： 平均的なケース分析を行うには、配列のすべての可能な順列を考慮し、簡単に見えないすべての順列にかかる時間を計算する必要があります。パーティションがO（n / 9）要素を1つのセットに配置し、O（9n / 10）要素を他のセットに配置する場合を検討することで、平均的なケースのアイデアを得ることができます。以下は、このケースの再発です。
T(n) = T(n/9) + T(9n/10) + (n)
上記の再発の複雑さは nLogn
クイックソートのスペースの複雑さ：
クイックソートで使用されるスペースは、使用されるバージョンによって異なります。
クイックソートのインプレースバージョンでは、次の場合でも、スペースの複雑さはO（log n）です。最悪の場合、次の戦略を使用して慎重に実装されます。
- インプレースパーティショニングが使用されます。この不安定なパーティションにはO（1）スペースが必要です。
- パーティション分割後、要素が最も少ないパーティションが最初に（再帰的に）ソートされ、最大でO（log n）スペースが必要になります。次に、もう一方のパーティションは末尾再帰または反復を使用してソートされますが、これは呼び出しスタックに追加されません。このアイデアは、前述のように、R。Sedgewickによって説明され、スタックの深さをO（log n）で制限します。