algorithm - デュアルソートとは

Question

誰かがデュアルソートアルゴリズムとは何か、そしてそれがどのように機能するかを正確に説明できますか? 私はウェブを検索しましたが、それに関する情報を見つけることができませんでした。宿題があり、それが何であるかを説明し、デュアルソートを使用してリストをソートするプログラムを作成する必要があります。

助けてくれてありがとう！

Answer 1

デュアル ピボット クイック ソートには 2 つのピボットの概念があり、通常のクイック ソートに非常に似ています。アルゴリズムが次のようなものになるよりも、ランダムな選択を想定してピボットを選択するいくつかのバリエーションがあります (結局のところ、まだ宿題であるため、明示的なコードは示しません)。重要なアイデアは、ランダムなピボット p1 と p2 を選択することです。p1 <= p2 と仮定すると、それ以外の場合はそれらの値が入れ替わります。次に、配列を 3 つの部分に並べ替えます。1 つ目は p1 未満、2 つ目は p1 と p2 の間の要素、3 つ目は p2 より大きい要素です。各部分の再帰より。

漸近的に、O(n lg n) の並べ替えが最適であることを知っていると推測できるように、このアルゴリズムはクイック 並べ替えと同時に実行されます。