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 to B.

Thanks in advance,
~Mack

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.