Теорема 9.1. Высота любого разрешающего дерева, сортирующего га элементов, есть fi(ralgra).

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

h га lg га - га lg е = Q (га lg га),

что и утверждалось.□

Следствие 9.2. Алгоритмы сортировки слиянием и с помощью кучи асимптотически оптимальны.

Доказательство. Они работают за время О (га lgra); в силу доказанной теоремы, эта оценка асимптотически неулучшаема. □

Упражнения

9.1-1 Какова наименьшая возможная глубина листа в разрешающем дереве алгоритма сортировки?

9.1-2 Докажите асимптотически точную оценку для lg(ra!) = ~Yk=i lg к без формулы Стирлинга, используя методы разд. 3.2.

9.1-3 Покажите, что не существует алгоритма сортировки, основанного на сравнениях, который работал бы за линейное время для половины из га! возможных входных последовательностей длины га. Как изменится ответ, если в этой задаче заменить 1/2 на 1/га? На 1/2п?

9.1-4 Профессор разработал компьютер, который поддерживает «тройные ветвления»: после одного-единственного сравнения аг- : aj управление может быть передано в одно из трёх мест программы, в зависимости от того, какое из соотношений выполнено: аг- < aj, аг- = aj или аг- > aj. Он надеется, что благодаря таким сравнениям сортировку га элементов можно провести асимптотически быстрее, чем за время fi(ralgra). Покажите, что профессор заблуждается.

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

9.1-6 Последовательность из га элементов, которую необходимо отсортировать, разбита на участки длины к. При этом любой элемент первого участка меньше любого элемента второго и т. д. (так

что остаётся лишь отсортировать элементы внутри участков). Покажите, что такая сортировка потребует не менее Q(nlgk) сравнений в худшем случае. (Указание: недостаточно сослаться на необходимость п/k раз сортировать участок длиной к.)

9.2. Сортировка подсчётом

Алгоритм сортировки подсчётом (counting sort) применим, если каждый из п элементов сортируемой последовательности - целое положительное число в известном диапазоне (не превосходящее заранее известного к). Если к = О(п), то алгоритм сортировки подсчётом работает за время О(п).

Идея этого алгоритма в том, чтобы для каждого элемента ж предварительно подсчитать, сколько элементов входной последовательности меньше ж, после чего записать ж напрямую в выходной массив в соответствии с этим числом (если, скажем, 17 элементов входного массива меньше ж, то в выходном массиве ж должен быть записан на место номер 18). Если в сортируемой последовательности могут присутствовать равные числа, эту схему надо слегка модифицировать, чтобы не записать несколько чисел на одно место.

В приводимом ниже псевдокоде используется вспомогательный массив С[1. .к] из к элементов. Входная последовательность записана в массиве А[1..п], отсортированная последовательность записывается в массив В[1. .п].

Counting-Sort(A, В, к)

1for г +- 1 to к

2do СИ <- О

3for j f- 1 to length[A]

4do C[A[j]]C[A[j]] + l

5> C[i] равно количеству элементов, равных г.

6for г +- 2 to к

7do СИ <- СИ + C[i - 1]

8> C[i] равно количеству элементов, не превосходящих г

9for j f- length[A] downto 1

10do B[C[A[j]]] <- A[j]

11C[A[j]] f- C[A[j]] - 1

Работа алгоритма сортировки подсчётом проиллюстрирована на рис. 9.2. После инициализации (строки 1-2) мы сначала помещаем в C[i] количество элементов массива А, равных г (строки 3-4), а затем, находя частичные суммы последовательности С[1], С [2],..., С [к], - количество элементов, не превосходящих г (строки 6-7). Наконец, в строках 9-11 каждый из элементов мае-

Рис. 9.2 Работа алгоритма counting-sort, применённого к массиву А[1. . 8], состоящему из натуральных чисел, не превосходящих к = 6. (а) Массив А и вспомогательный массив С после выполнения цикла в строках 3-4. (б) Массив С после выполнения цикла в строках 6-7. (в-д) Выходной массив В и вспомогательный массив С после одного, двух и трёх повторений цикла в строках 9-11. Зачернённые клетки соответствуют элементам массива, значения которым ещё не присвоены, (е) Массив В после окончания работы алгоритма.

сива А помещается на нужное место в массиве В. В самом деле, если все п элементов различны, то в отсортированном массиве число A[j] должно стоять на месте номер C[A[j]], ибо именно столько элементов массива А не превосходят A[j]; если в массиве А встречаются повторения, то после каждой записи числа A[j] в массив В число C[A[j]] уменьшается на единицу (строка 11), так что при следующей встрече с числом, равным A[j], оно будет записано на одну позицию левее.

Оценим время работы алгоритма сортировки подсчётом. Циклы в строках 1-2 и 6-7 работают за время О (к), циклы в строках 3-4 и 10-11 - за время О(п), а весь алгоритм, стало быть, работает за время О (к + п). Если к = О(п), то время работы есть О(п).

Для алгоритма сортировки подсчётом нижняя оценка разд. 9.1 - не препятствие, поскольку он не сравнивает сортируемые числа между собой, а использует их в качестве индексов массива.

Алгоритм сортировки подсчётом обладает важным свойством, называемым устойчивостью (it is stable). Именно, если во входном массиве присутствует несколько равных чисел, то в выходном массиве они стоят в том же порядке, что и во входном. Это свойство не имеет смысла, если в массиве записаны только числа сами по себе, но если вместе с числами записаны дополнительные данные, это оказывается важным. Более точно, представим себе, что мы сортируем не просто числа, а пары (t, ж), где t - число от 1 до к, а ж - произвольный объект, и хотим переставить их так, чтобы первые компоненты пар шли в неубывающем порядке. Описанный