Writing a sort comparison function
When you are writing a sort comparison function (say, to be passed to
ListView_SortItems or *gasp* to be used as
an IComparer), your comparison function needs to follow
these rules:
- Reflexivity:
Compare(a, a) = 0.
- Anti-Symmetry:
Compare(a, b) has the opposite sign of
Compare(b, a), where 0 is considered to
be its own opposite.
- Transitivity:
If
Compare(a, b) ≤ 0
and Compare(b, c) ≤ 0,
then Compare(a, c) ≤ 0.
Here are some logical consequences of these rules (all easily proved).
The first two are obvious, but the third may be a surprise.
- Transitivity of equality:
If
Compare(a, b) = 0
and Compare(b, c) = 0,
then Compare(a, c) = 0.
- Transitivity of inequality:
If
Compare(a, b) < 0
and Compare(b, c) < 0,
then Compare(a, c) < 0.
- Substitution: If
Compare(a, b) = 0, then
Compare(a, c) has the same sign as
Compare(b, c).
Of the original three rules,
the first two are hard to get wrong, but the third rule is
often hard to get right if you try to be clever in your comparison
function.
For one thing, these rules require that you implement a total order.
If you merely have a partial order, you must extend your partial
order to a total order in a consistent manner.
I saw somebody get into trouble when they tried to implement their
comparison function on a set of tasks, where some tasks have other
tasks as prerequisites. The comparison function implemented
the following algorithm:
- If
a is a prerequisite of b
(possibly through a chain of intermediate tasks),
then a < b.
- If
b is a prerequisite of a
(again, possibly through a chain of intermediate tasks),
then a > b.
- Otherwise,
a = b.
"Neither task is a prerequisite of the other, so I don't care what
order they are in."
Sounds great. Then you can sort with this comparison function and you
get the tasks listed in some order such that all tasks come after
their prerequisites.
Except that it doesn't work. Trying to sort with this comparison
function results in all the tasks being jumbled together
with apparently no regard for which tasks are prerequisites of which.
What went wrong?
Consider this dependency diagram:
a ----> b
c
Task "a" is a prerequisite for "b", and task "c" is unrelated to both
of them. If you used the above comparison function, it would declare
that "a = c" and "b = c" (since "c" is unrelated to "a" or "b"),
which in turn implies by transitivity that "a = b", which contradicts
"a < b", since "a" is a prerequisite for "b".
If your comparison function is inconsistent, you will get garbled results.
Moral of the story: When you write a comparison function, you really
have to know which items are less than which other items.
Don't just declare two items "equal" because you don't know which order
they should be in.
