CODEWITHSUNDEEP
algorithmsortingtopological-sort
Michael Kay
Michael Kay

Reputation: 163262

Topological sort based on a comparator (rather than a graph)

I have a set of items and a comparator function which defines a partial ordering -- given two items, it returns "=", "<", ">", or "no defined ordering" (say "<>"). I want to produce a sorted list of items that respects this partial ordering.

If I look for algorithms to do a topological sort, they generally start with a directed acyclic graph. But I don't have a DAG, and I can't see a simple way to construct one without doing a large number (N*N perhaps?) of comparisons. What I would like is some kind of QuickSort-like algorithm that works by comparing and swapping selected items in a list. Is there such an algorithm? I'm assuming most classical sorting algorithms would fail because of the indeterminism.

I thought of trying to use a classical sort algorithm and treating "<>" as "=", but it doesn't work because I can have the situation A < B, A <> C, B <> C, so I can't treat C as being equal to both A and B.

Any ideas or pointers?

Upvotes: 7

Views: 1133

Answers (1)

ardenit
ardenit

Reputation: 3890

You don't need to create a graph explicitly to use topological sort algorithm.

Let S be the set of elements you want to sort, and there is a partial order in S. Let used be the dictionary that maps each element from S to a boolean value (false by default) that will be true when we visit a 'node' with this element. Let stack be the stack of elements from S (empty by default).

Define a method dfs(x) (x is an element of S) that does the following:

  • Set used[x] to true

  • For each element y in S:

    • If used[y] is false and x is less than or equal to y (*):

      • Call dfs(y)

  • Add x to stack

Then:

  • For each element x in S:

    • If used[x] is false:

      • Call dfs(x)

After this loop, elements in stack will be ordered (first item to be popped from stack is minimal one (not necessarily minimum), last item is maximal one (not necessarily maximum)).

This algorithm obviously runs in O(n^2) because it's still a topological sort, just without creating graph explicitly.

(*): Like topological sort processes only edges that go from x to y and does not process cases where edge goes from y to x or there is no edge at all, this algorithm processes only 'less than or equal to' relations.

Upvotes: 4

Related Questions