pivot - ピボットの選択が悪いとクイックソートが O(n^2) になるのはなぜですか?

Question

たとえば、ピボットが配列内の最大値または最小値である場合などです。

2 つのポインターを使用するクイックソートの場合、1 つは左端から右に移動し、もう 1 つは右端から左に移動します。ポインターは、ピボットに対して位置がずれている要素を見つけると停止し、両方が停止すると、要素を交換して続行しますその位置から。しかし、ピボットの選択が悪いとクイックソートが O(n^2) になるのはなぜですか?

Answer 1

ピボットの選択が悪いとクイックソートが O(n^2) になるのはなぜですか?

ピボットとして常に最小の要素を選択するとします。クイックソートのトップレベルの反復では比較が必要になり、配列を sizeとn-1size の 2 つのサブ配列に分割します。最初のものはすでにソートされており、2 番目のものにクイックソートを再帰的に適用します。2 番目のものを分割するには、比較が必要になります。等々。1n-1n-2

全体として、(n-1) + (n-2) + ... + 1 = n * (n-1) / 2 = O(n^2)比較があります。

Answer 2

n 回同じ数のリストを試してください。
プリボットを見つける方法を選択してください。
何が起こっているか見てください。

（編集：いくつかのヒントを作成するには：
ピボットは常に同じであるため、ピボットを見つける方法に依存しません。
したがって、すべての反復で、n個の要素を持つ現在のリストに対してn回の比較が必要になり、 1 要素と n-1 要素を持つ 2 つのサブリストに n 個の現在の要素を含むリスト.
全体の操作の数をすばやく計算できます. 操作が必要ですn, n-1, n-2, ..., 2, 1.
正式には でありsum from i=1 to n over i, を確認するための式を知っておく必要がありますO(n*n))

Answer 3

選択したピボットが再帰のたびにサブセット内の最大値であった場合、アルゴリズムは読み取ったすべてのレコードをピボットの下のサブセットに単純に移動し、空でないパーティションを 1 つだけ続行します。この新しいサブセットのサイズは、1 つだけ少なくなります。

その場合、クイックソート操作は選択ソートに似ています。最大値を見つけて、その場所に配置し、次の反復で残りのデータに進みます。違いは、選択ソートが最大 (または最小) データ ポイントを検索することです。最悪のケースのクイック ソートでは、最大値が選択され、それが実際に最大値であることを発見します。

私の知る限り、これは非常にまれなケースです。