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

8 Answers 8

13
$\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
    Commented 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
    Commented Dec 16, 2013 at 15:57
  • 4
    $\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
    Commented Feb 13, 2014 at 0:39
  • 2
    $\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$ Commented Jun 7, 2019 at 1:49
5
$\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
    Commented 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$
1
$\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$
1
$\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$
1
$\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$
1
$\begingroup$

Well it is very much possible to sort using some non transitive comparer. But it depends on what non transitivity means for you. For situation A > B && B > C there are 3 possible scenarios:

  • A > C (that's transitivity)
  • A >= C (soft non transitivity)
  • A and C in any relation (hard non transitivity)

If you have transitive comparer, you can use fast sorting algorithms in n*log(n). If you have a soft nontransitive comparer, you can use slower n^2 sorting algorithms. For example bubble sort:

private T[] BubbleSort<T>(IEnumerable<T> values, IComparer<T> comparer) {
    T[] result = values.ToArray();
    for(int i = result.Length - 1; i >= 0; i--) {
        for(int j = 0; j < i; j++) {
            int c = comparer.Compare(result[j], result[j + 1]);
            if(c >= 0) {
                T tmp = result[j];
                result[j] = result[j + 1];
                result[j + 1] = tmp;
            }
        }
    }
    return result;
}

For hard nontransitivity, you cannot use any sorting algorithm and expect some reasonable outcomes.

The reason why you need an n^2 algorithm is, beacause then the algo actually compares every element with one another. In n*log(n) it takes advantage of transitivity.

Note in the above algo, we swap the elements even for c == 0, so even when they are equal regarding the soft nontransitive comparer. That way all elements eventually get to the ones they can compare to.

$\endgroup$
1
  • $\begingroup$ This answer has multiple problems, one of which is not the author's fault: we need to wait for the OP to clarify what flavour of sortedness they intend to establish by sorting wrt a non-transitive order. I suspect it is 1-sortedness as defined by @gnasher729 in one of their answers. The distinction of three kinds of non-transitivity is bogus. The first is not non-transitive and any instance of the second being anything but the third would violate antisymmetry. The remainder of the answer doesn't add anything to existing answers. $\endgroup$
    – Kai
    Commented Jan 24 at 23:12
-1
$\begingroup$

In general, sorting algorithms rely on the transitive property of the comparison function to correctly order elements. Transitivity ensures that if A is less than B and B is less than C, then A must be less than C. This property guarantees that the sorting algorithm can consistently compare and order elements.

However, in your case, the tolerant comparator function violates transitivity. Despite this violation, it is still possible to use a sorting algorithm with this non-transitive comparison function. One way to achieve this is by modifying the sorting algorithm to handle the non-transitive nature of the comparator.

One approach is to perform multiple passes through the array, each time considering a different subset of the elements that are within the tolerance range. The idea is to divide the array into smaller parts and sort them separately. Within each part, the transitivity violation is still present, but we only compare elements within that specific part. By doing so, we can ensure that the sorting algorithm produces a "correctly sorted" output based on the given comparator.

For example, let's consider the array [1, 4, 2, 3, 5] with the tolerant comparator. We can perform two passes. In the first pass, we consider elements within a tolerance range of 1. This would result in the following subsets: [1, 2], [4, 3], [5]. Within each subset, the tolerance is satisfied, and we can sort them independently. After sorting each subset, we combine them back together, resulting in [1, 2, 3, 4, 5], which is correctly sorted based on the given comparator.

So, to summarize, while the tolerant comparator violates transitivity, it is still possible to use a sorting algorithm by modifying it to handle the non-transitive nature. By dividing the array into subsets and sorting them separately, we can ensure a correctly sorted output based on the given comparator.

$\endgroup$
3
  • $\begingroup$ This answer has many problems. I see many sentences that superficially look good, but it doesn't propose any specific algorithm. I find it unclear exactly what is being proposed. How do you partition the array elements into subsets? You don't say. There are many ways to do it, it is not obvious which to choose. Why does [1,4,2,3,5] get partitioned into [1,2], [4,3], [5] instead of [1], [2,3], [4,5]? Also the example is bogus. If you sort [4,3] with this intransitive comparator, the result may be [4,3], as that is already sorted according to the comparator. $\endgroup$
    – D.W.
    Commented Jan 19 at 20:48
  • $\begingroup$ Other answers already appear to have proven that the last sentence of this answer is wrong. See, e.g., the example in cs.stackexchange.com/a/65956/755; as far as I can tell, the technique proposed here does not ensure a correctly sorted output when run on the example in that answer. $\endgroup$
    – D.W.
    Commented Jan 19 at 20:49
  • $\begingroup$ If you happen to have used AI to help you with this answer, I encourage you to refer to our guidelines on using AI to support you in writing answers: stackoverflow.com/help/ai-policy $\endgroup$
    – D.W.
    Commented Jan 19 at 20:50

Your Answer

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

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