Топологическая сортировка на основе компаратора (а не графика)

Question

У меня есть набор элементов и функция компаратора, которая определяет частичное упорядочение - при заданных двух элементах возвращается «=», «<», «>» или «без определенного порядка» (скажем, «<>») ). Я хочу создать отсортированный список элементов, который учитывает это частичное упорядочение.

Если я ищу алгоритмы для топологической сортировки, они обычно начинаются с направленного ациклического графа c. Но у меня нет DAG, и я не могу найти простой способ его создания, не выполняя большое количество (возможно, N * N) сравнений. То, что я хотел бы, это какой-то QuickSort-подобный алгоритм, который работает путем сравнения и обмена выбранных элементов в списке. Есть ли такой алгоритм? Я предполагаю, что большинство классических алгоритмов сортировки потерпит неудачу из-за неопределенности.

Я думал о том, чтобы попытаться использовать классический алгоритм сортировки и трактовать «<>» как «=», но он не работает, потому что я может иметь ситуацию A C, B <> C, поэтому я не могу трактовать C как равное как A, так и B.

Любые идеи или указатели

Answer 1

Вам не нужно явно создавать граф для использования алгоритма топологической сортировки.

Пусть S будет набором элементов, которые вы хотите отсортировать, и существует частичный порядок в S. Пусть used будет словарём, который отображает каждый элемент из S в логическое значение (false по умолчанию), которое будет true, когда мы посетим «узел» с этим элементом. Пусть stack будет стеком элементов из S (по умолчанию пусто).

Определите метод dfs(x) (x является элементом S), который выполняет следующие действия:

• Установить used[x] на true

• Для каждого элемента y in S:

  • Если used[y] равно false и x меньше или равно y (*):

    • Вызовите dfs(y)

• Добавить x к stack

Затем:

• Для каждого элемента x in S:

  • Если used[x] равно false:

    • Вызов dfs(x)

После этого l oop, элементы в stack будут упорядочены (первый извлекаемый элемент из stack минимальный ( не обязательно минимальный ), последний элемент является максимальным (не обязательно максимальным)).

Этот алгоритм, очевидно, работает в O (n ^ 2), потому что это все еще топологическая сортировка, просто без явного создания графа. * 10 84 *

(*): Подобно топологической сортировке, обрабатываются только ребра, которые go от x до y, и не обрабатываются случаи, когда ребро переходит от y до x или ребро вообще отсутствует этот алгоритм обрабатывает только отношения «меньше или равно».