マージソートとクイックソートの実行時間の理解

Question

マージソートとクイックソートの両方について、私はそれらが最悪になるシナリオを考え出しています。私が正しければ、すべてがソートされるとソートの最悪のケースO（nlogn）をマージします。クイックソートの最悪のケースは、ピボットが最も最適でない場所にあり、配列がソートされているので、O（n^2）になります。私はこれが最初に正しいかどうか疑問に思っていたので、そうでなければ私を修正してください。 私の実際の質問は、クイックソートのピボットが配列の途中にある場合、配列はO（n^2）になるためにどのように見えますか？

Answer 1

クイックソートの最悪のケースは、ピボットがソートされる残りの値のすべてより小さいか大きい場合です。この場合、再帰の各レベルで残りの値から1つのアイテムだけが削除され、時間の複雑さはO（n^2）になります。

基本的なマージソートの場合、トップダウンまたはボトムアップの場合、移動回数は常に同じです。比較の数はデータパターンに依存します。サイズnの2回のランをマージすると、最悪の場合の比較数は2n-1です（2つのランから1つを除いた各要素が比較され、要素が1つだけ残っている場合は比較対象がないのでコピーされます）最善のケースは、ある実行の要素のすべてがもう1つの実行の最初の要素よりも小さい場合です。その場合、データのソートまたは逆ソートの場合など、比較の回数はn回です。

Answer 2

クイックソートをエミュレートすることができます。ピボットを選択するたびに、最悪の場合のパフォーマンスを保証するために0,1,2、...が連続していることを確認してください。

これは、配列を所定の位置に分割する前にピボット値を配列の先頭にスワップする通常のピボットアルゴリズムを前提としています。この場合、ピボットをピックして最小の残りのアイテムにするので、分割する必要はありません。

class Cell: 
    def set(self, v): 
     self.v = v 

def worst_case_quicksort(xs, i): 
    xs = xs[:] 
    for i in xrange(len(xs)): 
     p = (len(xs) - i) // 2 
     xs[i+p].set(i) 
     xs[i], xs[i+p] = xs[i+p], xs[i] 

xs = [Cell() for _ in xrange(20)] 
worst_case_quicksort(xs, 0) 
print [x.v for x in xs] 

出力は次のようになります：

[1, 11, 3, 19, 5, 13, 7, 17, 9, 15, 0, 2, 4, 6, 8, 10, 12, 14, 16, 18]