16
$\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$
4
  • $\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, 2013 at 18:01
  • 3
    $\begingroup$ I suspect that some non-transitive comparator used in some sorting algorithm could cause an infinite loop. $\endgroup$ Dec 15, 2013 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$ Dec 19, 2013 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, 2016 at 20:16

6 Answers 6

12
$\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$
4
  • 1
    $\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, 2013 at 23:41
  • 4
    $\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, 2013 at 15:57
  • 3
    $\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, 2014 at 0:39
  • $\begingroup$ I ran into this a while back and found that bubble sort actually works just fine, since it only ever compares adjacent elements. $\endgroup$ Jun 7, 2019 at 1:49
4
$\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
  • 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, 2014 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$
0
$\begingroup$

I second the answers given so far (equality and comparison operators but fulfill the mathematical requirements and not doing so can cause nasty bugs that are hard to spot). But I want to mention a method that sometimes solves the problem that people try to solve using an invalid comparator like the one mentioned in the OP. Assume you have a list of float numbers and you consider them "sufficiently equal" when they're closer than 1e-4. Then define the equality operator and the comparator based on their rounded values:

rounded(x) = 1e-4 * Round(1e4 * x) // where Round rounds to integers
x1 :== x2 iff rounded(x1) == rounded(x2)
x1 :< x2 iff rounded(x1) < rounded(x2)
..

Such and equality operator is valid for grouping methods and the corresponding comparator can be used for sorting. The results are reasonable.

When the numbers have a wide range of magnitudes you can also format each number into a string with the usual formatting options (exponential or smart with 4 significant digits or so), and define equality based on those strings:

str(x) := sprintf("%4g", x)
x1 :== x2 iff str(x1) == str(x2)
x1 :< x2 iff str(x1) != str(x2) and x1 < x2
..

Please forgive me if these snippets are not valid pseudocode, I hope they're good enough to explain the idea.

$\endgroup$
0
$\begingroup$

Define “correctly sorted”. Here’s an attempt: An array is k-sorted if $a_i <= a_j$ whenever $i <= j <= i+k$. If <= is transitive then any 1-sorted array is (n-1)-sorted.

With the definition of <= in the question, assume the array contains one element equal to zero, one element equal to 1+epsilon, and all other elements from epsilon to 1. Then there is exactly one pair of elements that don’t compare equal. If we don’t compare these two elements then all comparisons result in “equal”, so an algorithm that doesn’t take O(n^2) steps might produce a result that is not even two-sorted.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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