Пишем компаратор для сортировки

Это перевод Writing a sort comparison function. Автор: Реймонд Чен.

Когда вы пишете функцию сравнения (например, для передачи в функцию сортировки ListBox), убедитесь, что ваша функция удовлетворяет следующим условиям:

• Рефлексивность: Compare(a, a) = 0.
• Анти-симметричность: Compare(a, b) имеет знак, противоположный знаку Compare(b, a).
• Транзитивность: если Compare(a, b) ≤ 0 и Compare(b, c) ≤ 0, то Compare(a, c) ≤ 0.

Из этих правил следует несколько легко-доказуемых следствий. Первые два довольно очевидны, а вот третье может оказаться неожиданностью.

• Транзитивность равенства: если Compare(a, b) = 0 и Compare(b, c) = 0, то Compare(a, c) = 0.
• Транзитивность неравенстра: если Compare(a, b) < 0 и Compare(b, c) < 0, то Compare(a, c) < 0.
• Подстановка: если Compare(a, b) = 0, то Compare(a, c) имеет тот же знак, что и Compare(b, c).

Из этих трёх правил довольно тяжело реализовать неверно первые два. Но вот с третьим правилом можно легко напортачить.

Заметим, что эти правила требуют от вас введения полного порядка на своих элементах. Если у вас есть только частичный порядок - вы должны расширить его до полного каким-либо согласованным и единообразным образом. Я видел, как у кое-кого возникли проблемы, когда они реализовывали компаратор для набора задач. При этом завершение одной из задач могло быть необходимым условием для заверешния других задач. Функция сравнения реализовывала такой алгоритм:

• Если a является необходимым для b (возможно через цепочку промежуточных зависимостей), тогда a < b.
• Если b является необходимым для a (опять-таки, возможно через цепочку промежуточных зависимостей), тогда a > b.
• А в противном случае a = b. "Ни одна из задач не является необходимым условием для другой, поэтому меня не волнует, в каком порядке они находятся."

Звучит отлично. Тогда с такой функцией вы можете рассортировать список задач так, чтобы задачи, зависящие от других задач, были бы в списке после своих зависимостей.

Только вот это не будет работать. Попытка сортировки списка задач с таким компаратором приведёт к выводу списка, в котором все задачи идут в совершенно случайном порядке, без учёта зависимостей друг от друга. Что же пошло не так?

Посмотрите на такую диагарамму зависимости:

a ----> b

c

Элемент "a" предшествует "b", а элемент "c" не связан ни с "a", ни с "b". Если бы вы использовали функцию сравнения выше, то она бы объявила вам, что "a = c" и "b = c" (поскольку "c" не связано с "a" или "b"), откуда, в свою очередь, по транзитивности равенства следует, что "a = b", что противоречит "a < b", потому что "a" является необходимым условием для "b". Если ваш компаратор непоследователен или противоречив, вы всегда будете получать искажённые результаты.

Мораль истории: когда вы пишете функцию сравнения, вы должны быть точно уверены в том, какой элемент идёт до, а какой после. Не объявляйте два элемента "равными" друг другу просто потому, что вы не знаете, в каком порядке они должны идти.