CODEWITHSUNDEEP
algorithmset
arashka
arashka

Reputation: 1325

Sort Algorithm for a set of elements knowing pair order

Here is a problem that I'm seeking an algorithmic solution for. Suppose we have a set of n elements, A1, A2, ..., An And we have a set of rules like A1 > A2, A1 < A3 and etc. Rules are enough for writing the sorted list by hand. Is there a known method for doing the sort? I don't want to do a bubble sort like loop, I'm looking for a standard solution. Any ideas? A name would be enough for me!

Thanks in advance.

Upvotes: 3

Views: 271

Answers (2)

Niklas B.
Niklas B.

Reputation: 95308

Comparison-based sort algorithms will only work if you have a total ordering, that is if for every pair x, y with x != y, we know whether x < y or y < x. What you have is a partial ordering on your set of elements and what you are looking for is a toplogical ordering of the elements according to that partial order.

To find it, interpret your input as a graph with edges (a, b) where a < b is an input pair. Then do a DFS on that graph:

dfs(x):
  if x is visited: return
  for every rule x < y or y > x:
    dfs(y)
  add x to front of output

output = []
for every element x:
  dfs(x)

The runtime is O(n + m) where n is the number of elements (nodes) and m is the number of rules (edges).

Upvotes: 4

Alice
Alice

Reputation: 3986

Sure, take your pick!

Any comparison sort will work; just put your rules into a big if/else statement in a single function, and the comparison sort will be more than happy to sort them as you like.

Upvotes: -1

Related Questions