algorithm - クイックソート複雑度計算

Question

1. 配列のすべての要素が同じ値を持つ場合、クイック ソートのパーティションは q のどの値を返しますか? 私の答え: O(n^2)
2. 要件に従って配列がすでにソートされている場合のクイックソートアルゴリズム。 私の答え: O(n^2)
3. 配列が要件の逆順で既にソートされている場合のクイックソートアルゴリズム。 myAns: O(n log n)
4. クイックソートに使用される分割アルゴリズムが、要素を 1-α と α に分割したとします。ここで、0< α ≤1/2、α は定数です。再帰関係を導出し、その複雑さを計算します。 myAns: O(n log n)

次の項目についても回答してください。

クイックソートで使用される配列の分割に使用される Hoare 分割アルゴリズムについて、適切な例を挙げて説明してください。

Answer 1

1. クイックソートの実装方法によって異なります。

2. ピボット選択戦略に依存します。

3. ピボット選択戦略に依存します。

4. 右。