14
$\begingroup$

Is it possible to use a sorting algorithm with a non-transitive comparison, and if yes, why is transitivity listed as a requirement for sorting comparators?

Background:

  • A sorting algorithm generally sorts the elements of a list according to a comparator function C(x,y), with

    \begin{array}{ll} C(x,y) = \begin{cases} -1 & {\text{if}}\ x\prec y \\ 0 & {\text{if}}\ x\sim y \\ +1 & {\text{if}}\ x\succ y \\ \end{cases} \end{array}

    The requirements for this comparator are, as far as I understand them:

    • reflexive: $\forall x: C(x,x)=0$
    • antisymmetric: $\forall x,y: C(x,y) = - C(y,x)$
    • transitive: $\forall x,y,z, a: C(x,y)=a \land C(y,z)=a \Rightarrow C(x,z)=a$
    • C(x,y) is defined for all x and y, and the results depend only on x and y

    (These requirements are always listed differently accross different implementations, so I am not sure I got them all right)

Now I am wondering about a "tolerant" comparator function, that accepts numbers x,y as similar if$ |x - y| \le 1$: \begin{array}{ll} C(x,y) = \begin{cases} -1 & {\text{if}}\ x\lt y-1 \\ 0 & {\text{if}}\ |x - y| \le 1 \\ +1 & {\text{if}}\ x\gt y+1 \\ \end{cases} \end{array}

Examples: both [ 1, 2, 3, 4, 5] and [1, 4, 3, 2, 5] are correctly sorted in ascending order according to the tolerant comparator ($C(x,y) \le 0$ if x comes before y in the list)
but [1, 4, 2, 3, 5] is not, since C(4,2)=1

This tolerant comparator is reflexive and antisymmetric, but not transitive.

i.e. C(1,2) = 0 , c(2,3) = 0, but C(1,3) = -1, violating transitivity

Yet I cannot think of any sorting algorithm that would fail to produce a "correctly sorted" output when given this comparator and a random list.

Is transitivity therefore not required in this case? And is there a less strict version of transitivity that is required for the sorting to work?

Related questions:

$\endgroup$
  • $\begingroup$ I think quicksort with "always choose middle" for the pivot would fail using this comparator on [3, 2, 1]. $\endgroup$ – G. Bach Dec 15 '13 at 18:01
  • 2
    $\begingroup$ I suspect that some non-transitive comparator used in some sorting algorithm could cause an infinite loop. $\endgroup$ – Karolis Juodelė Dec 15 '13 at 18:42
  • 1
    $\begingroup$ What would you consider as a sorted list (i.e. the required output)? In the usual case, there are two equivalent conditions: $a_i \leq a_{i+1}$, and $a_i \leq a_j$ for all $i \leq j$. $\endgroup$ – Yuval Filmus Dec 19 '13 at 13:24
  • $\begingroup$ @G.Bach I think quicksort will actually fail completely if your array has n times 3, one time 2, n times 1, and the middle 2 is used as the first pivot, no matter what happens afterwards. $\endgroup$ – gnasher729 Nov 12 '16 at 20:16
10
$\begingroup$

You asked: Can we run a sorting algorithm, feeding it a non-transitive comparator?

The answer: Of course. You can run any algorithm with any input.

However, you know the rule: Garbage In, Garbage Out. If you run a sorting algorithm with a non-transitive comparator, you might get nonsense output. In particular, there is no guarantee that the output will be "sorted" according to your comparator. So, running a sorting algorithm with a non-transitive comparator is not likely to be useful in the way you were probably hoping for.

As a counterexample, running insertion sort on the input list $[3, 2, 1]$ using your comparator would leave the list unchanged -- yet the resulting output list is not in sorted order (according to your comparator).

$\endgroup$
  • $\begingroup$ my first thought was that the list [3,2,1] is in sorted order according to my comparator, so of course the sort should leave it unchanged; but I might have been using the wrong definition of sorted. I just compare each element with its direct neighbors, but that might be too weak a restriction for considering a list sorted $\endgroup$ – HugoRune Dec 15 '13 at 23:41
  • 3
    $\begingroup$ @HugoRune Well, that's an interesting point. What do you mean by sorted? If you can show a sorting algorithm will terminate given a non-transitive comparator, and that whenever the algorithm terminates, some condition is true, and that condition is what you take sorting to be... then of course that algorithm will sort your list every time, for that definition of sortedness. If the comparator isn't transitive, it may not make sense to take a definition of sorted which requires pairwise comparison of all elements in the sorted list. $\endgroup$ – Patrick87 Dec 16 '13 at 15:57
  • 2
    $\begingroup$ @HugoRune, with "only neighbors are compared" you'll probably need a custom sort. The standard algorithms assume transitivity to avoid redundant comparisons. Or you can embed your non-transitive order in a transitive one. Or perhaps you are looking for something along the lines of topological sorting? $\endgroup$ – vonbrand Feb 13 '14 at 0:39
3
$\begingroup$

Given a set of elements and a binary ordering relation, transitivity is required to totally order the elements. In fact, transitivity is even required to define a partial order on the elements. http://en.m.wikipedia.org/wiki/Total_order

You would need a much broader definition of what "sorted" means in order to sort elements without transitivity. It is hard to be self-consistent. Another answer says "In particular, there is no guarantee that the output will be 'sorted' according to your comparator." But we can actually say something much stronger. You are guaranteed that the output is not sorted according to your comparator.

Say that you have a non-transitive comparator that tells you $a<b$, $b<c$, and $c<a$. Which element is the smallest one? No matter which one you choose, your comparator will tell you another element is smaller.

$\endgroup$
  • 1
    $\begingroup$ I interpreted the question to be asking about sorting using partial orderings (such that a comparisons which say things are unequal are transitive, but those which regard items are indistinguishable are not). Sorting based on partial ordering is sometimes useful, but in the worst case requires N(N-1)/2 comparisons. Any sorting algorithm which in the worst case does less than N(N-1)/2 comparisons will be unable to correctly rank partially-ordered items for reasons described in my answer. $\endgroup$ – supercat Feb 12 '14 at 23:40
2
$\begingroup$

It sounds as though what you want is to arrange items such that all discernible rankings are correct, but items which are close might be considered "indistinguishable". It is possible to design sort algorithms which will work with such comparisons, but unless there are limits to how many comparisons may report that things are indistinguishable, there is no way to avoid having them require N(N-1)/2 comparisons. To understand why, pick some number N and any sorting algorithm that does less than N(N-1)/2 comparisons. Then populate a list L[0..N-1], setting each element L[I] to I/N and "sort" it using your comparator (the minimum value will be 0 and the maximum (N-1)/N, so the difference will be (N-1)/N, which is less than 1).

Because there are N(N-1)/2 pairs of items that could be compared, and the sort didn't do that many comparisons, there must be some pair of items that was not directly compared against each other. Replace whichever one of these ended up being sorted first by 1, and the other with -1/N, revert all items to their initial position, and repeat the sorting operation. Every single comparison operation will yield zero, just as it did the first time, so the same comparisons will be performed and items will end up in the same sequence. For the list to be correctly sorted, the "1" would have to sort after the "-1/N" (since they differ by more than one) but since the sorting algorithm would never compare those two items directly against each other, it would have no way of knowing that.

$\endgroup$
0
$\begingroup$

Fill an array of n elements with the values n, n-1, n-2, ..., 2, 1. Then try to sort using the "straight insertion" algorithm. You'll find that each element is considered equal to the element just before it, and therefore isn't moved. The result of the "sort" is the same array.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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