3.3. СОРТИРОВКА С ПОМОЩЬЮ СРАВНЕНИЙ
Здесь мы изучим задачу упорядочения последовательности из элементов, взятых из линейно упорядоченного множества о структуре которых ничего не известно. Информацию об этой последовательности можно получить только с помощью операции сравнения двух элементов. Сначала мы покажем, что любой алгоритм,
упорядочивающий с помощью сравнений, должен делать по крайней мере сравнений на некоторой последовательности длины . Пусть надо упорядочить последовательность, состоящую из различных элементов Алгоритм, упорядочивающий с помощью сравнений, можно представить в виде дерева решений так, как описано в разд. 1.5. На рис. 1.18 изображено дерево решений, упорядочивающее последовательность Далее мы предполагаем, что если элемент а сравнивается с элементом в некотором узле дерева решений, то надо перейти к левому сыну узла при и к правому — при
Как правило, алгоритмы сортировки, в которых для разветвления используются сравнения, ограничиваются сравнением за один раз двух входных элементов. В самом деле, алгоритм, который работает на произвольном линейно упорядоченном множестве, не может никак преобразовать входные данные, поскольку при самой общей постановке задачи операции над данными "не имеют смысла". Так или иначе, мы докажем сильный результат о высоте любого дерева решений, упорядочивающего последовательность из элементов.
Лемма 3.1. Двоичное дерево высоты содержит не более листьев.
Доказательство. Элементарная индукция по Нужно лишь заметить, что двоичное дерево высоты составлено из корня и самое большее двух поддеревьев, каждое высоты не более
Теорема 3.4. Высота любого дерева решений, упорядочивающего последовательность из различных элементов, не меньше
Доказательство. Так как результатом упорядочения последовательности из элементов может быть любая из перестановок входа, то в дереве решений должно быть по крайней мере листьев. По лемме 3.1 высота такого дерева должна быть не меньше
Следствие. В любом алгоритме, упорядочивающем с помощью сравнений, на упорядочение последовательности из элементов тратится не меньше сравнений при некотором и достаточно большом
Доказательство. Заметим, что при
так что
По формуле Стерлинга точнее приближает функция так что служит хорошим приближением нижней границы числа сравнений, необходимых для упорядочения последовательности из элементов.