Is "In C++, comparator should return false if its arguments are equal." all you should know about comparators in C++?

Definitely NOT.

What's the requirement of the custom comparator in STL?

It should be a Strict Weak Ordering. In other words, let the comparator be $$$f$$$, and $$$f(x, y)=true$$$ means $$$x< y$$$, then:

1. $$$f(x, x)$$$ must be false (Irreflexivity)

2. If $$$f(x, y)$$$ is true, then $$$f(y, x)$$$ must be false. (Antisymmetry)

3. If $$$f(x, y)=true$$$ and $$$f(y, z)=true$$$, then $$$f(x, z)$$$ must be true. (Transitivity)

4. If $$$f(x, y)=false$$$, $$$f(y, x)=false$$$, $$$f(y, z)=false$$$ and $$$f(z, y)=false$$$, then $$$f(x, z)=false$$$ and $$$f(z, x)=false$$$. (Transitivity of equivalence)

In fact, Antisymmetry can be deduced by Irreflexivity and Transitivity, so we can ignore it.

Here are some examples that these rules aren't satisfied:

Why do we need to follow these rules?

Imagine you are the designer of the STL function sort. It's a template function, so you know nothing about the type provided by the user, except the comparator, which means "<".

Is a single "<" enough? Is it necessary for users to provide ">", "≤", "≥" and "=" as well?

In fact, all other comparators can be expressed by "<":

• $$$x > y$$$ means $$$y < x$$$;

• $$$x \le y$$$ means $$$y \not < x$$$;

• $$$x \ge y$$$ means $$$x \not < y$$$;

• $$$x = y$$$ means $$$x \not < y$$$ and $$$y \not < x$$$. That's why the fourth rule above is called Transitivity of equivalence. We can also say "$$$x$$$ and $$$y$$$ are incomparable" if $$$x \not < y$$$ and $$$y \not < x$$$.

What does "sort" mean exactly?

A sequence is sorted with respect to a comparator comp if for any iterator it pointing to the sequence and any non-negative integer n such that it + n is a valid iterator pointing to an element of the sequence, comp(*(it + n), *it) (or *(it + n) < *it) evaluates to false.

std::sort — cppreference.com

Let's say the sorted array is $$$a_1, a_2, \ldots, a_n$$$, does "sorted" mean "$$$\forall 1\le i\le n-1, a_{i+1}\not < a_i$$$"?

It does, if the comparator is a Strict Weak Ordering.

But if the comparator isn't a Strict Weak Ordering, even "$$$\forall 1\le i\le n-1, a_{i+1}\not < a_i$$$", there can be inversions ($$$a_j < a_i, 1\le i\le j\le n$$$).

Why is Irreflexivity needed?

STL just chose one from Irreflexivity and Reflexivity , and that's the difference between "strict" ($$$<$$$) and "non-strict" ($$$\le$$$).

As this choice is made, if we provide a comparator without Irreflexivity, every two equal elements will be considered as an inversion, thus sorting will become impossible.

Why is Transitivity needed?

In fact, only "no $$$\le$$$ cycle with non-equal elements" is needed. Formally, there is no $$$x_1, x_2,\ldots, x_k$$$ satisfying $$$x_1 \le x_2 \le \ldots \le x_k \land x_k \le x_1 \land \exists 1\le i, j\le k, x_i < x_j)$$$.

If the comparator doesn't form any cycles, but Transitivity is not satisfied, we can add Transitivity to it, which won't affect the sorting.

Why is Transitivity of equivalence needed?

Have you ever considered why can't we do the topological sort on a DAG in $$$O(n\log n)$$$ (make it an interactive problem, so that you don't need to read all the edges)?

That's because Transitivity of equivalence is not guaranteed.

In fact, the best query complexity for sorting a poset (partially ordered set) is $$$O(n(w+\log n))$$$, where $$$w$$$ is the width of the poset (or you can treat it as the size of the maximum independent set in a DAG). Reference: Sorting and Selection in Posets.

If we consider incomparable elements as a single element, Strict Weak Ordering will become a strict total order, or a strict partial order with the width of $$$1$$$, thus the query complexity will be $$$O(n\log n)$$$.

Transitivity of equivalence is used in all $$$O(n\log n)$$$ comparison sorting algorithms. Let's see where Transitivity of equivalence is used in bubble sort and quicksort for example.

In bubble sort, it is required that "if there are any inversions, at least one of them is two adjacent elements". But this may be not true without Transitivity of equivalence. In the $$$f(x, y)=x+1 < y$$$ and $$$3, 2, 1$$$ example, the only inversion is $$$(3, 1)$$$, and they are not adjacent.

In the Partitioning step of quicksort with fat partition, the incomparable elements are not handled, thus Transitivity of equivalence is needed.

A problem which needs to be careful with Transitivity of equivalence

I only know links of this problem on some Chinese OJs, if anyone knows links of this problem on other OJs, please make a comment.

There is a practical statement in LOJ10003, and a mathematical version in LG2123.

Practical version

There are $$$n$$$ jobs, each job consists of two parts, the first part must be done in center A, the second part must be done in center B, each center can do at most one job in one time, the second part of the $$$i$$$-th job can be started only if the first part of the $$$i$$$-th job is already done.

The time needed for each part of each job is given, please arrange the order of doing these jobs, in order to minimize the time when all jobs are done.

Mathematical version

There is an array of $$$n$$$ elements, each element has two positive attributes $$$a_i$$$ and $$$b_i$$$. You have to rearrage the elements (but you can't change the corresponding relationship between each pair of $$$a_i$$$ and $$$b_i$$$), the goal is to minimize $$$c_n$$$, where:

The solution

Let's consider two adjacent elements $$$i$$$ and $$$i+1$$$. Now, we are going to decide whether to swap these two elements or not.

Let $$$pre$$$ be $$$c_{i-1}$$$, $$$sum$$$ be $$$\sum_{j=1}^{i-1}a_j$$$ which are both condidered as constants. Let $$$a_i$$$, $$$b_i$$$, $$$a_{i+1}$$$, $$$b_{i+1}$$$ refer to the value before swapping, no matter whether we swapped them or not.

If we don't swap them, then $$$c_i$$$ will be $$$\max(pre, sum+a_i)+b_i$$$, and $$$c_{i+1}$$$ will be $$$\max(\max(pre, sum+a_i)+b_i, sum+a_i+a_{i+1})+b_{i+1}=\max(pre+b_i+b_{i+1}, sum+a_i+b_i+b_{i+1}, sum+a_i+a_{i+1}+b_{i+1})$$$.

If we swap them, then $$$c_{i+1}$$$ will be $$$\max(pre+b_{i+1}+b_i, sum+a_{i+1}+b_{i+1}+b_i, sum+a_{i+1}+a_i+b_i)$$$.

Let's compare them. We can know that $$$\max(a_{i+1}+b_{i+1}+b_i, a_{i+1}+a_i+b_i) < \max(a_i+b_i+b_{i+1}, a_i+a_{i+1}+b_{i+1})$$$ is a necessary condition for swapping is better. And this condition is equal to $$$\max(-a_i, -b_{i+1}) < \max(-a_{i+1}, -b_i)$$$, thus equal to $$$\min(a_i, b_{i+1}) > \min(a_{i+1}, b_i)$$$.

That's to say, "swapping $$$i$$$ and $$$i+1$$$ when $$$\min(a_i, b_{i+1}) \le \min(a_{i+1}, b_i)$$$ won't make $$$c_n$$$ smaller".

Then, the solution comes:

Sort the elements by some comparator, such that $$$\min(a_i, b_{i+1}) \le \min(a_{i+1}, b_i)$$$ holds for all $$$1\le i\le n-1$$$.

But, if we just use $$$f(i, j)=\min(a_i, b_j)<\min(a_j, b_i)$$$ as the comparator, something will go wrong.

For example:

and

They are two different permutations, both satisfy $$$\forall 1\le i\le n-1, \min(a_i, b_{i+1}) \le \min(a_{i+1}, b_i)$$$, but $$$c_4$$$ in the first example is $$$13$$$, $$$c_4$$$ in the second example is $$$14$$$.

Do you know why it is wrong?

In fact, this comparator doesn't satisfy Transitivity of equivalence.

In the example above, $$$\begin{cases}\min(3,1)=\min(1,4)\\ \min(1,5)=\min(2,1)\end{cases}$$$, but $$$\min(3,5)\ne \min(2,4)$$$.

The correct comparator should be:

The above function is a Strict Weak Ordering.

Let's prove the correctness of this algorithm using the correct comparator:

1. There is at least one optimal permutation which is a sorted array under this comparator. Proof: Otherwise, apply bubble sort to the optimal permutation to get a sorted array, $$$c_n$$$ won't be larger.

2. All sorted arrays under this comparator are optimal. Proof: All sorted arrays can be made by swapping incomparable elements from the optimal sorted array mentioned above. And swapping incomparable elements won't change $$$c_n$$$.

In the second step, we used Transitivity of equivalence. If it's not satisfied, the proof will go wrong.

There is another comparator, which is known as "Johnson's rule". This "rule" is equivalent to this comparator:

This is also a Strict Weak Ordering, and $$$f(i, j)=true$$$ implies $$$\min(a_i, b_j)\le\min(a_j, b_i)$$$, so it can solve this problem.

As a conclusion, The "sorting considering swapping adjacent elements" method works like this:

1. $$$P(x, y)=true$$$ is a necessary condition for "swapping $$$x$$$ and $$$y$$$ is better".

2. $$$f(x, y)=true$$$ is a sufficient condition for $$$P(x, y)=false$$$, and $$$f$$$ is a Strict Weak Ordering for the elements in the array.

3. Then, sort the array with $$$f$$$ as the comparator, the sorted array is optimal.