Sorting a poset?

Question

There are a huge number of sorting algorithms out there, but most of them only work on totally-ordered sets because they assume that any two elements are comparable. However, are there any good algorithms out there for sorting posets, where some elements are uncomparable? That is, given a set S of elements drawn from a poset, what is the best way to output an ordering x₁, x₂, ..., x_n such that if x_i ≤ x_j, i ≤ j?

Answer 1

There's a paper titled Sorting and Selection in Posets available on arxiv.org which discusses sorting methods of order O((w^2)nlog(n/w)), where w is the "width" of the poset. I haven't read the paper, but it seems like it covers what you are looking for.

Answer 2

Topological sort is well-suited to sorting a partially ordered set. Most algorithms are O(n^2). Here's an algorithm from 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)

There's a helpful video example. Most Unix-like systems have the tsort command. You could solve the video's brownie example with tsort as follows:

$ 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

Answer 3

I'd start with selection-exchange sort. That's O(n^2) and I don't think you'll do better than that.