そこには膨大な数のソートアルゴリズムがありますが、それらのほとんどは、2つの要素が同等であると仮定しているため完全に順序付けされたセットでのみ動作します。しかし、いくつかの要素が比較できないposetsをソートするための優れたアルゴリズムはありますか？すなわち、posetから引き出された要素の集合Sが与えられると、ある出力するための最良の方法は何か順序X は、、...、 X X NようにX I ≤ Xならj、i ≤j？posetをソートする？
arxiv.orgにはSorting and Selection in Posetsというタイトルの論文があり、オーダーO（（w^2）nlog（n/w））のソート方法について説明しています。ここでwはposetの「幅」です。私は論文を読んでいないが、あなたが探しているものをカバーしているようだ。
リンクありがとうございます！これは非常に有望に見えます！ – templatetypedef
私は選択交換ソートから始めます。それはO（n^2）だと私はあなたがそれよりもうまくいくとは思わない。
Topological sortは、部分的に順序付けされたセットをソートするのに適しています。ほとんどのアルゴリズムはO（n^2）です。ここにはWikipediaのアルゴリズムがあります。
L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
remove a node n from S
add n to tail of L
for each node m with an edge e from n to m do
remove edge e from the graph
if m has no other incoming edges then
insert m into S
if graph has edges then
return error (graph has at least one cycle)
else
return L (a topologically sorted order)
helpful video exampleがあります。ほとんどのUnixライクなシステムにはtsortコマンドがあります。あなたはtsortでビデオのブラウニーの例を次のように解決できます：
$ cat brownies.txt
preheat bake
water mix
dry_ingredients mix
grease pour
mix pour
pour bake
$ tsort brownies.txt
grease
dry_ingredients
water
preheat
mix
pour
bake
これはちょうどトポロジカルな並べ替えですか？ –
@ jleedev-トポロジカルな並べ替えでそれを行うことができるのは、Sの要素のすべてのペアが互いに先験的にどのように比較されているかを知っている場合のみです。それ以外の場合は、すべての比較をO（| S |^2）時間行う必要があります。 – templatetypedef