language-agnostic - ポーズセットを並べ替えていますか?

Question

膨大な数の並べ替えアルゴリズムがありますが、それらのほとんどは、任意の 2 つの要素が比較可能であると想定しているため、完全に順序付けられたセットでのみ機能します。ただし、一部の要素が比較できない場合に、ポーズセットをソートするための優れたアルゴリズムはありますか? つまり、poset から引き出された要素のセット S が与えられた場合、x _i ≤ x _{j , i ≤ j となる順序 x 1} , x ₂ , ..., x _nを出力する最良の方法は何でしょうか?

Answer 1

arxiv.org で利用可能なPosets のソートと選択というタイトルの論文があります。ここでは、w がポーズセットの「幅」である O((w^2)nlog(n/w)) の並べ替え方法について説明しています。私は論文を読んでいませんが、あなたが探しているものをカバーしているようです.

Answer 2

選択交換ソートから始めます。それは O(n^2) であり、それ以上のことはないと思います。