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?

  • 8
    $\begingroup$ Is your "less than" relation really an order relation? If so, any old sorting algorithm (taking the values in your matrix as the result of comparisons) will do. If not, no "sorted order" has to exist (think of the dominance relation on paper-scissors-rock). $\endgroup$ – vonbrand Feb 25 at 14:57
  • $\begingroup$ You could also (less efficiently) count the number of 1s in each matrix row/column and then sort the objects according to that key. $\endgroup$ – user253751 Feb 25 at 15:05

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.