но провести тщательное исследование числа сравнений, поскольку теоретический анализ этого вопроса позволит нам более глубоко проникнуть во внутреннюю природ} процессов сортировки, а также поможет отточить мастерство для решения задач, более близких к практике, которые могут возникнуть перед нами в будущем. Исключим из рассмотрения метод поразрядной сортировки, в котором совсем не выполняется сравнений, и ограничимся обсуждением методов, основанных только на абстрактном линейном отношении порядка "<" между ключами, рассмотренном в начале этой главы. Для простоты мы также ограничимся случаем различных ключей, а это значит, что при любом сравнении ключей Ki и Kj возможны лишь два исхода: либо Ki < Kj, либо Ki > Kj. (Распространение результатов такого анализа на общий случай, когда допускаются равные ключи, приводится в упр. 3-12.) Ограничения на время выполнения в худшем случае рассматриваются в работах Fredman, Willard, J. Computer и Syst. Sci. 47 (1993), 424-436, Ben-Amram, Galil, J. Сотр. Syst. Sci. 54 (1997), 345-370 и Thorup, SODA 9 (1998), 550-555.

Возможны и другие эквивалентные варианты постановки задачи сортировки посредство.м сравнений. Если есть п грузов и весы с двумя чашами, то каково минимальное число взвешиваний, необходимое для того, чтобы расположить грузы по порядку в соответствии с весом, если в каждой чаше весов помещается только один груз? Или же, если в некотором турнире участвуют п игроков, то каково наименьшее число пар1Ш1х встреч, достаточное для того, чтобы распределить места между соревнующимися в предположении, что силы игроков можно линейно упорядочить (ничейные результаты не допускаются).

Методы сортировки п элементов, удовлетворяющие указанным ограничениям, можно представить с помощью структуры расширенного бинарного дерева, такого, которое показано на рис. 34. Каждый внутренний узел (изображенный в виде кружочка) содержит два индекса "г: j" и означает сравнение ключей Ki и Kj. Левое поддерево этого узла соответствует последующим сравнениям, которые необходимо вьшолнить, если Ki < Kj, а правое поддерево - тем действиям, которые необходимо предпринять, если Ki > Kj. Каждый внешний узел дерева (изображенный в виде прямоугольника) содержит перестановку ai а2 ... а„ множества {1,2,..., п}, а это обозначает, что было установлено упорядочение

Kai < Ка2 < " • < Ка,„ .

(Если взглянуть на путь от корня к этому внешнему узлу, то каждое из п - 1 соотношений ATq, < Kai+i, где 1 < г < п, - результат некоторого сравнения ai.ai+i или ai+i.ai на этом пути.)

Так, на рис. 34 представлен метод сортировки, суть которого состоит в том, чтобы сначала сравнить Ki с Л2; если Ki > К2, то продолжать (двигаясь по правому поддереву) сравнивать АГ2 с АГз, а затем, если К2 < Кз, сравнить Ki с К3; наконец, если Ki > Кз, становится ясно, что К2 < Кз < Ki. Реальный алгоритм сортировки будет также перезаписывать ключи в массиве, но нас интересуют только сравнения, поэтому мы игнорируем все перезаписи данных. При сравнении Ki с Kj в этом дереве всегда имеются в виду исходные ключи Ki и Kj, а не те ключи, которые могли занять г- и j-ю позиции в массиве в результате перемещения записей.

Возможны и избыточные сравнения; например, на рис. 35 нет необходимости сравнивать 3:1, поскольку из неравенств Ki < К2 и К2 < Кз следует Ki < К3. Ни-

Уровень О

Уровень 1

Уровень 2 12 3(1

Уровень 3

Рис. 34. Дерево сравнений для сортировки трех элементов.

Рис. 35. Пример избыточного сравнения.

какая перестановка не может соответствовать левому поддереву узла 3:1 на рис. 35, так что эта часть алгоритма никогда не будет выполняться! Поскольку нас интересует минимальное число сравнений, можно считать, что избыточные сравнения не выполняются. С этого момента мы будем иметь дело со структурой расширенного бинарного дерева, в котором каждому внешнему узлу соответствует некоторая перестановка. Все перестановки исходных ключей возможны, и каждая перестановка определяет единственный путь от корня к внешнему узлу; отсюда вытекает, что в дереве сравнений для сортнровкп п элементов без избыточных сравнений имеется ровно п\ внешних узлов.

Оптимизация в наихудшем случае. Первая естественным образом возникающая задача - найти деревья сравнений, минимизирующие максимальное число выполняемых сравнений. (Позже мы рассмотрим среднее число сравнений.)

Пусть 5(п) - минимальное число сравнений, достаточное для сортировки п элементов. Если все внутренние узлы в дереве сравнений располагаются на уровнях < к, то очевидно, что в дереве не может быть более 2* внешних узлов. Следовательно, полагая к = 5(п), имеем

п! < 2(").

Поскольку 5(п) нюю оценку:

5(п)> rign!l. Заметим, что по формуле Стирлинга

flgn!] =nlgn-n/In2+ilgn + (9(l),

целое число, можно записать эту формулу иначе, получив ниж-

следовательно, необходимо выполнить около nlgn сравнений. Соотношение (1) часто называют теоретико-информационной нижней оценкой, поскольку специалист в области теории информации сказал бы, что в процессе сортировки проверяется Ign! "бит информации"; каждое сравнение дает не более одного бита информации. Такие деревья, как на рис. 34, называют также "вопросниками" (questionnaires); их математические свойства исследованы в книге Claude Picard, Theorie des Questionnaires (Paris: Gauthier-Villars, 1965).

Из всех рассмотренных нами методов сортировки три метода требуют меньше всего сравнений: бинарные вставки (см. раздел 5.2.1), выбор из дерева (см. раздел 5.2.3) и простое двухпутевое слияние, описанное в алгоритме 5.2.4L). Нетрудно видеть, что максимальное число сравнений для метода бинарных вставок равно

J5(n) = 5]ngA;1=nrignl-2r«"l+l (3)

(см. упр. 1.2.4-42), а максимальное число сравнений для двухпутевого слияния определено в упр. 5.2.4-14. Оказывается (см. раздел 5.3.3), что для метода выбора из дерева верхняя оценка числа сравнений либо такая же, как для метода бинарных вставок, либо такая же, как для двухпутевого слияния, в зависимости от вида дерева. Во всех трех случаях имеем асимптотическое значение nlgn; объединяя верхнюю и нижнюю оценки для 5(п), получим

Иш = 1. (4)

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

п = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

[Ignll = 0 1 3 5 7 10 13 16 19 22 26 29 33 37 41 45 49

В{п) = О 1 3 5 8 11 14 17 21 25 29 33 37 41 45 49 54

L{n) = 0 1 3 5 9 11 14 17 25 27 30 33 38 41 45 49 65

Здесь В{п) и L{n) относятся соответственно к методам бинарных вставок и слияния списков. Можно показать, что В{п) < L{n) при любом п (см. упр. 2).

Как видно из приведенной выше таблицы, 5(4) = 5, но 5(5) может равняться либо 7, либо 8. В результате снова приходим к задаче, поставленной в начале раздела 5.2. Каков наилучший способ сортировки пяти элементов? Возможна ли сортировка пяти элементов при помощи всего семи сравнений?

Такая сортировка возможна, но сам способ найти не так просто. Начинаем так же, как при сортировке четырех элементов посредством слияний, сравнивая сначала ATj: АГг, затем - АГз: АГ4, а затем - наибольшие элементы обеих пар. Эти сравнения порождают конфигурацию, которую можно изобразить диаграммой

/7. • <