Algorithm for sorting loosely comparable data?

Question

Let's say I have an unsorted list of four objects: [B, C, A, D].

All four objects are of the same type, and:

  (A > B),
  (C > D),
  (A != C or D)
  (B != C or D)
  (C != A or B)
  (D != A or B).

By != I mean that they are neither less-than, equal-to, or greater-than the other objects.

I need to "sort" the list such that A will always come before B, and C will always come before D. Beyond those two requirements, I have no demand on the ordering of the list; therefore, given the previously described list, the sort function should return either [A, B, C, D] or [C, D, A, B].

As for the cause of this problem, I am trying to sort an array of java.lang.Class objects based on their relationships to each other. For example, if A is the super-class/super-interface of B, then A is less-than B. If A extends/implements B, then is A greater-than B. If A is B, then obviously A equals B. Otherwise, A is completely non-comparable toB.

Answer 1

Build a graph. For each two elements x and y such that x > y, add a directed edge from x to y. In your example you'd have A -> B and C -> D. Then run topological sort on this graph. The topological sort returned will be a possible solution.