ランダム化された3の中央値によるクイックソートは、ランダム化されたクイックソートよりもかなり優れていますか? 質問する

クイックソートの実装でパーティションを選択するためのさまざまなアプローチに関する質問に答えていたところ、正直どう答えたらよいかわからない質問が浮かびました。少し数学的な要素が多く、このサイトで質問するのは適切ではないかもしれません。そのため、この質問を移動する必要がある場合はお知らせください。喜んで他の場所に移行します。

ピボットをランダムに均一に選択するクイックソートの実装は、期待されるO(n lg n)時間で実行されることがよく知られています（このことの証明があります）。ウィキペディアで）。しかし、乱数生成のコストのため、多くのクイックソート実装ではピボットをランダムに選択せず、代わりに「3つの要素の中央値」アプローチに依存しています。このアプローチでは、3つの要素が決定論的に選択され、その中央値がピボットとして選択されます。これは、最悪の場合、 O(n ^{2 )に縮退することが知られています（}この素晴らしい論文たとえば、最悪のケースの入力を生成する方法についてなど)。

さて、私たちが組み合わせるこれら 2 つのアプローチでは、シーケンスから 3 つの要素をランダムに選択し、その中央値をピボットの選択として使用します。これにより、通常のランダム クイックソートとは少し異なる証明を使用して、平均ケースの実行時間が O(n lg n) になることもわかっています。ただし、この特定のクイックソート実装で、n lg n 項の前の定数係数が何であるかはわかりません。通常のランダム クイックソートの場合、Wikipedia には、ランダム クイックソートの実際の実行時間は最大で 1.39 n lg n の比較 (lg を 2 進対数として使用) が必要であると記載されています。

私の質問は次のとおりです:「3つの中央値」ランダムクイックソートを使用して行われた比較の数の定数係数を導き出す方法を誰か知っていますか？? さらに一般的に言えば、ランダム化された k の中央値アプローチを使用したクイックソートの定数係数を表す式はありますか? このアプローチに、他のランダム化されたクイックソート実装よりも比較が少ない「スイートスポット」があるかどうかを確認するのは興味深いと思うので、興味があります。つまり、ランダム化された 6 の中央値ピボット選択を使用したランダム化クイックソートでは、比較が最も少なくなると言えるとしたらクールではないでしょうか。または、ピボット要素をランダムに選択する必要があると断言できるとしたらどうでしょうか。