QuickSortは、ピボットとして最大要素を選択した場合、常に2次ランタイムを持っていますか？

Question

クイックソートアルゴリズムがあり、常にピボットとして最小（または最大の）要素を選択する場合。既にソートされたデータセットを提供している場合、「すでにソートされた」リストが昇順であるか降順であるかに関係なく、常に最悪のパフォーマンスを得ることができると思いますか？

私の考えは、あなたが常にあなたのピボットのために常に小さな要素を選択するなら、あなたのピボットに関連するサブセットが常にソートされるように選択されたサブセットが常にであるため、あなたの「すでにソートされた」入力が昇順または下降によってソートされないかどうかは、あなたの「すでにソートされた」入力が問題ではないということです同じサイズ？

Answer 1

QuickSortの最悪のケースの複雑さは$ Theta（n^2）$です。これは、セットを分割するピボットを選択して、1つのグループに1人のメンバーしかないようにすることで達成されます。悪いピボットピッキングアルゴリズムでは、ソートされたセットの一方の端を選択することで簡単に実現できます。あなたの仮定は正しいです。

Answer 2

はい！あなたは絶対に正しいと思っています！そして、Yuval Filmusで正しく言及されているように、実行時間は$ Theta（n^2）$になります

Answer 3

1つのサブアレイには0ドルまたは1ドルの要素があり、もう1つのサブアレイには$（n-1）$要素があります。したがって、それは$ o（n^2）$：$$ t（n）= t（n-1）+t（0）+o（n）= o（n^2）$$です