Last week and the week before, I showed a common example of an incorrect comparison function for pairs:

struct Point { int x, y; };
bool compare(const Point& p, const Point& q)
{
   return p.x < q.x && p.y < q.y;
}

and said that I would explain what is wrong with it. I also said that I would explain why the notion of approximate equality causes problems with sorting.

Both of these examples cause trouble for the same two fundamental reasons:

1. When you define an ordering relation for sorting purposes, that relation implicitly defines a notion of "unordered" that covers the case where compare(a, b) and compare(b, a) are both false.
2. This notion of "unordered" has to be an equivalence relation in order for sorting to work correctly.

With these reasons in mind, let's look first at approximate equality. Tempting though the notion might be, as soon as you decide to consider "equal" any two values that are closer than a given threshold, you get into trouble. The trouble occurs when a and b are close enough together to be considered equal, but just barely so, and b and c are also close enough to be considered equal, but also just barely so. In that case, it should be easy to imagine that even though a is "equal" to b and b is "equal" to c, a and c are not equal.

Such circumstances cause sorting to fail, and as a result, even if you decide to use approximate equality under other circumstances, you must not do so for sorting purposes.

Now let's look at our compare function. On the surface, it makes sense to say that a point is "less than" another point if both of its corresponding coordinates are less than those in the other point. However, consider what that rule does to the notion of "unordered:" It says that two points are unordered whenever their coordinates compare in opposite directions.

In other words, if p.x ≤ q.x and p.y ≥ q.y, or if p.x ≥ q.x and p.y ≤ q.y, the two points are "unordered." With this definition, it is not hard to find three points p, q, and r such that p and q are unordered, q and r are unordered, but p and r are ordered. For example, (0, 0) is unordered with both (0, n) and (n, 0) for any value of n ≥ 0, but it is "less than" (m, n) whenever both m > 0 and n > 0. Therefore, (0, 0) is unordered with both (0, 1), which is unordered with (1, 1), but (0, 0) is "less than" (1, 1).

One way of avoiding trouble when you try to define an order relation for sorting is to start by asking what "unordered" means as a concept, in the context of the data structure that you are trying to sort. It can be useful to think of this notion as a funny way of spelling "equal." For example, when we are sorting character strings, we often think of strings that differ only by whether letters are upper- or lower-case as "equal." Similarly, when we set out to sort pairs of numbers, we should start by thinking about what notion of "equality" we want to use when we are sorting.

One reader suggested an interesting possibility: We could sort numbers based on how far they are from a given point, such as (0, 0). This idea would lead to the following comparison function:

bool compare(const Point& p, const Point& q)
{
   return (p.x*p.x + p.y*p.y) < (q.x*q.x + q.y*q.y);
}

This comparison function treats all points the same distance from (0, 0) as being "equal." In effect, it does not distinguish at all between the points on any circle centered on (0, 0), and sorts all points based on the size of the circle that includes each point.

Many readers will consider this notion of sorting points to be rather weird, but at least it meets the requirements — something that the version we presented at the beginning of this not does not do. Another common solution to this problem is to compare points in "dictionary order:"

bool compare(const Point& p, const Point& q)
{
   return p.x < q.x || (p.x == q.x && p.y < q.y);
}

We can rewrite this function so that it does not need to use == at all:

bool compare(const Point& p, const Point& q)
{
   return p.x < q.x || (!(q.x < p.x) && p.y < q.y);
}

This rewrite relies on the fact that one of p.x < q.x, p.x == q.x, or q.x < p.x will always be true, so that if p.x < q.x and q.x < p.x are both ruled out, only p.x == q.x remains.

Written in this form, this function lets us generalize from < on a single pair of elements to < on multiple pairs of elements, and does so in a way that does not require us to define > or =.