Сортировка сета?

Question

Существует огромное количество алгоритмов сортировки, но большинство из них работают только на полностью упорядоченных множествах, потому что они предполагают, что любые два элемента сравнимы. Тем не менее, есть ли хорошие алгоритмы для сортировки поз, где некоторые элементы несопоставимы? То есть, учитывая набор S элементов, взятых из набора, каков наилучший способ вывести порядок x ₁ , x ₂ , ..., x _n такой, что если x _i & le; x _j , i & le; J

Answer 1

На arxiv.org доступна статья под названием Сортировка и выборка в позах , в которой рассматриваются методы сортировки порядка O ((w ^ 2) nlog (n / w)), где w - это ширина"из сета.Я не читал газету, но похоже, что она охватывает то, что вы ищете.

Answer 2

Топологическая сортировка хорошо подходит для сортировки частично упорядоченного набора. Большинство алгоритмов O (n ^ 2). Вот алгоритм из Википедии:

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)

Есть полезный пример видео . Большинство 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

Answer 3

Я бы начал с сортировки выбора-обмена. Это O (n ^ 2), и я не думаю, что ты справишься лучше.