Началось всё с проблемы синхронизации данных между клиентом и БД на сервере.
В БД имеется таблица и связь этой таблицы самой с собой (ID, ParentID), в результате чего имеется возможность, выражаясь языком математики, хранить в БД лес некоторых объектов.
Клиент, имея выборку из этой таблицы, может помечать ветви деревьев для удаления, после чего начинается процесс синхронизации. Если допустить удаление каждой строки в произвольном порядке, может возникнуть ошибка, когда родительский объект, имеющий потомков, не может быть удалён без порождения аномалии удаления, когда в таблице остаются записи-"сироты", ссылающиеся на уже несуществующую запись.
Таким образом, возникла
задача. Массив помеченных на удаление записей таблицы, в общем случае содержащих лес объектов, нужно упорядочить так, чтобы первыми в массиве оказались крайние потомки (листья деревьев), затем их непосредственные родители и т.д. до корней деревьев.
Задачу попытались решить без особых раздумий -- воспользоваться библиотечной функцией sort, реализующей быструю сортировку Хоара. Аргументом функции является функция сравнения двух элементов (компаратор), возвращающая для любых x,y -1, если x<y, 1 если x>y и 0 в остальных случаях.
Была написана функция сравнения, которая возвращала следующие значения:
- если x -- предок любого уровня для y, то вернуть 1, поскольку предок должен быть "больше" потомка и в результате сортировки оказаться в конце массива;
- если x -- потомок любого уровня для y, то вернуть -1, поскольку потомок должен быть "меньше" предка и в результате сортировки оказаться в начале массива;
- в остальных случаях возвращать 0, поскольку либо x и y -- один и тот же объект, либо эти объекты не находятся в общей иерархии, и их взаимный порядок для нас безразличен.
Сортировка выполнялась
неправильно. Проверили отладчиком функцию-компаратор -- во всякий вызов для всех сравниваемых пар, которые получались в результате работы алгоритма сортировки, компаратор возвращал правильное значение. Тем не менее, общий результат сортировки был неправильным.
Поскольку заведомо известно и проверено на других задачах, что библиотечная функция сортировки реализована верно, все подозрения сосредоточились на компараторе.
Математически мы имеем множество элементов, между которыми установлено бинарное отношение порядка. Для принципиального решения задачи сортировки элементов такого множества (по Д. Кнуту "Искусство программирования", т.3)
необходимо выполнить два условия:
- должен действовать закон трихотомии: либо истинно a<b, либо a=b, либо a>b, но никогда не могут быть истинными два или три этих отношения вместе;
- должен действовать закон транзитивности: если a<b и b<c, то a<c.
Несложно доказать, что для любых a,b из нашего массива закон трихотомии выполняется. Также несложно доказать, что для любых a,b,c из нашего массива закон транзитивности также выполняется. Но быстрая сортировка Хоара не работает.
Детальный анализ быстрой сортировки Хоара показывает следующее.
На каждом шаге алгоритма имеются 3 активных позиции в массиве: левая и правая границы и опорный элемент. Левая граница сдвигается вправо до тех пор, пока либо не зайдёт за правую границу, либо не найдётся находящийся на левой границе элемент, больший опорного. Аналогично правая граница сдвигается влево либо до захода за левую границу, либо до нахождения элемента, меньше опорного. Если границы не зашли друг за друга, то элементы на левой и правой границах меняются местами.
Ключевым моментом здесь является то, что обменивающиеся местами элементы
не сравниваются между собой. Между тем заданное над множеством бинарное отношение таково, что даже если a=b и b=c, то может быть a<c. Если a -- потомок любого уровня для c, и b -- элемент из параллельной ветви дерева, то, в самом деле, нам безразлично, будет ли a расположено раньше b или наоборот, будет ли c расположено раньше b или наоборот, но совершенно не безразлично взаимное расположение a и c. Именно здесь алгоритм и допускает ошибку, выполняя неправильный обмен.
На нашем множестве с описанным бинарным отношением условия Д. Кнута для решения задачи методом быстрой сортировки Хоара
не являются достаточными (что, впрочем, Д. Кнут и не обещал, но и не указал специально для этого метода). Алгоритм неявно полагает, что если не выполняются оба неравенства a<b<c, то справедливы неравенства a>=b>=c и их можно будет заменить на c<=b<=a. Это, в самом деле, справедливо, но в то же время c<=b<=a не означает (c<b<a или c=b=a или c<b=a или c=b<a).
При этом всякий алгоритм сортировки, который
всегда выполняет сравнение
каждого элемента с каждым (например, пузырьковый алгоритм), т.е. являющийся как минимум квадратичным по сложности (или с некоторыми улучшениями), произведёт правильную сортировку.
Можно пойти и другим путём: сменить отношение, например, сортировать все элементы по убыванию глубин в деревьях -- тогда можно будет применить и быструю сортировку.
Думаю, мораль сей басни очевидна.
