How to sort objects based only on “less than” relationships?

Question

Say I have n objects, each with an unknown value, and a n by n matrix Z. Such that Z(i,j)=1 if the value of object i is less than the value of object j, and Z(i,j)=0 otherwise. How can I sort these n objects, given only the matrix Z?

Answer 1

What you are looking for is a comparison sort. Please take a look at that article.

---

Let us state clearly the requirement for any two given objects, object i and object j when they appear in the final sorted list. Object i should occur before object j if Z(i, j) = 1. Object i can occur before or after object j if Z(i, j) = Z(j, i) = 0.

As vonbrand mentioned, we should assume that the matrix Z specifies a well-defined "less than" relation or, in terms of math, a total strict-order on the values of the objects. Otherwise, the given objects may not be sorted.

• Z[i, j] = 0 if Z[j, i] = 1. Otherwise, we cannot sort object i and object j.
• Z[j, i] = 0 if Z[i, k] = 1 and Z[k, j] = 1 for some k. Otherwise, we cannot sort object i, j and k (think of paper-scissors-rock).

---

Assume that Z specifies a well-defined "less than" relation. Then it also defines a "$\le$" comparison operation naturally. Namely, if Z(j, i) = 0, then object i $\le$ object j. So we can apply any comparison sort to sort the given $n$ object.

Almost all sorting algorithms are comparison sorts. For example, quicksort, mergesort, insertion sort, selection sort and bubble sort. A notable exception is counting sort.