CODEWITHSUNDEEP
algorithmsortingmath
Tryer
Tryer

Reputation: 4050

Sorting given pairwise orderings

I have n variables (Var 1 ... Var n) and do not know their exact values. The n choose 2 pairwise ordering between these n variables are known. For instance, it is known that Var 5 <= Var 9, Var 9 <= Var 10 and so on for all pairs. Further, it is also known that these pairwise orderings are consistent and do not lead to a degenerate case of equality throughout. That is, in the above example the inequality Var 10 <= Var 5 will not be present.

What is the most efficient sorting algorithm for such problems which gives a sorting of all variables?

Upvotes: 3

Views: 1055

Answers (2)

Yann TM
Yann TM

Reputation: 2075

The question is not so much how to sort (use the standard sort of your language) but how to feed the sort criterion to the sorting algorithm.

In most languages you need to provide a int comparison (T a, T b) where T is the type of elements, that returns -1, 0 or 1 depending on who is larger.

So you need a fast access to the data structure storing (all) pairwise orderings, given a pair of elements.

So the question is not so much will Var 10 <= Var 5 be present (inconsistent) but more is Var 5 <= Var 10 ensured to be present ? If this is the case, you can test presence of the constraint in O(1) with a hash set of pairs of elements, otherwise, you need to find a transitive relationship between a and b, which might not even exist (it's unclear from OP if we are talking of a partial or total order, i.e. for all a,b we ensure a < b or b < a or a = b (total order).

With roughly worst case N^2 entries, this hash is pretty big. Building it still requires exploring transitive links which is costly.

Following links probably means a map of elements to sets of (immediately) smaller elements, when comparing a to b, if (map(a) contains b) or (map(b) contains a) you can answer immediately, otherwise you need to recurse on the elements of map(a) and map(b), with pretty bad complexity. Ultimately you'll still be cumulating sets of smaller values to build your test.

Perhaps if you have a low number of constraints a <= b, just applying a permutation of a and b when they do not respect the constraint and iterating over the constraints to fixpoint (all constraints applied in one full round with no effect) could be more efficient. At least it's O(1) in memory.

A variant of that could be sorting using a stable sort (preserves order of incomparable entries) several times with subsets of the constraints.

Last idea, computing a Max with your input data is O(number of constraints), so you could just repeatedly compute the Max, add it at the end of the target, remove constraints that use it, rinse and repeat. I'd use a stack to store the largest element up to a given constraint index, so you can backtrack to that rather than restart from scratch.

Upvotes: 3

hemflit
hemflit

Reputation: 2999

Pairwise ordering is the only thing that any (comparison-based) sort needs anyway, so your question boils down to "what's the most efficient comparison-based sorting algorithm".

In answer to that, I recommend you look into Quicksort, Heapsort, Timsort, possibly Mergesort and see what will work well for your case in terms of memory requirements, programming complexity etc.
I find Quicksort the quickest to implement for a once-off program.

Upvotes: 6

Related Questions