Разрешающее дерево сортировки сравнениями

Введение

Особенности реализации алгоритмов сортировки; сортировка за линейное время

В предыдущих разделах были рассмотрены различные алгоритмы, которые могут отсортировать п чисел за время О (п ×log n). Алгоритмы сортировки слиянием (merge sort) и сортировки с помощью кучи (heap sort) работают за такое время в худшем случае, а у алгоритма быстрой сортировки таковым является среднее время работы. Оценка O (n ×log n) точна: для каждого из этих алгоритмов можно предъявить последовательность из п чисел, время обработки которой будет W(n ×log n).

Все упомянутые алгоритмы проводят сортировку, основываясь исключительно на попарных сравнениях элементов, поэтому их иногда называют сорти­ровками сравнением (comparison sort). В дальнейшем будет доказано, что алгоритм такого типа сортирует п элементов за время не меньше W(n ×log n) в худшем случае. Тем самым алгоритмы сортировки слиянием и с помощью кучи асимптотически оптимальны: не существует алгоритма сортировки сравнением, который превосходил бы указанные алгоритмы более чем в конечное число раз.

Три алгоритма сортировки – сортировка подсчётом, цифровая сортировка и сортировка вычерпыванием могут работать за линейное время. Разумеется, они улучшают оценку W(n ×log n) за счёт того, что используют не только попарные сравнения, но и внутреннюю структуру сортируемых объектов, т.е. дополнительную априорную информацию. Без использования дополнительной информации сортировка за линейное время невозможна.

Говорят, что алгоритм сортировки основан на сравнениях, если он никак не использует внутреннюю структуру сортируемых элементов, а лишь сравнивает их и после некоторого числа сравнений выдаёт ответ (указывающий истин­ный порядок элементов).

На рис. 2.8 изображено разрешающее дерево (decision tree), соответствующее сортировке последовательности из трёх элементов с по­мощью алгоритма сортировки вставками.

Рисунок 2.8 – Разрешающее дерево сортировки вставками

Поскольку число перестановок из трёх элементов равно 3! = 6, у дерева должно быть не менее 6 листьев. Поскольку двоичное дерево высоты h имеет не более 2 ^h листьев, имеем n! ≤ 2 ^h. Логарифмируя это неравенство по основанию 2 и пользуясь неравенством п! > (п / е) ^п, вытекающим из формулы Стирлинга , получаем, что

что и утверждалось. Наилучшее время работы алгоритма сортировки сравнениями есть O (n ×log n), причем эта оценка не может быть асимптотически улучшена (т.к. доказано, что нижний предел для любой сортировки сравнениями, не использующей дополнительной информации есть W(n ×log n)).