0.0 I

0.0 0.1 0 2 0.3 0.4 0.5 0.6 0,7 0.8 0,9 1.0 Рис. 37. Функция 1+в-2.

внешних узлов на уровне g - 1 и 27V - 2 на уровне q, где q = \lgN]. (Корень находится на нулевом уровне.) Таким образом, минимальная длина внешнего пути равна

(q - 1)(2» -N)+ q{2N - 2») {q + 1)N - 2". (34)

Имеется еше один интересный способ охарактеризовать минимальную длину пути: расширенное бинарное дерево имеет минимальную длину внешнего пути тогда и только тогда, когда существует такое число I, что все внешние узлы находятся на уровнях I и I + I (см. упр. 20).

Если положить q = IgN + в, где О < < 1, то формула минимальной длины внешнего пути примет вид

N{\gN + 1+в -2). (35)

График функции 1 + в - 2 изображен на рис. 37; при О < < 1 она принимает положительные, но очень малые значения, не превышающие

1 - (1 + In In 2)/ In 2 = 0.08607 13320 55934+. (36)

Таким образом, минимальная возможная средняя длина пути, которая получается в результате деления (35) на N, не может быть меньше \gN и больше IgN + 0.0861. (Этот результат впервые получил Э. Глисон (А. Gleason) в неопубликованной заметке 1956 года.)

Если теперь положим N = п\, то получим нижнюю оценку среднего числа сравнений по всем схемам сортировки. Оценка асимптотически приближается к

Ign!-Ь 0(1) =nlgn-n/ln2-bO(logn). (37)

Пусть F{n) - среднее число сравнений, выполняемых алгоритмом сортировки посредством вставок и слияния; имеем

п=1234 5 6 7 8

Нижняя граница (34) = О 2 16 112 832 6896 62368 619904 n!F(n)= 0 2 16 112 832 6912 62784 623232

Итак, сортировка посредством вставок и слияния оптимальна в обоих смыслах при п < 5, однако при п = 6 такой метод в среднем требует 6912/720 = 9.6 сравнений вместо возможных согласно нижней оценке 6896/720 = 9.577777... сравнений. Немного поразмыслив, нетрудно понять, почему это так: некоторые "удачные" перестановки шести эле.ментов сортируются методом вставок и слияний всего за восемь сравнений, и тогда дерево сравнений имеет внешние узлы на трех, а не на двух уровнях. Из-за этого увеличивается суммарная длина пути. В упр. 24 показано, что можно построить процедуру сортировки шести элементов, требующую всегда девять или десять сравнений; следовательно, этот метод превосходит метод вставок и слияний в среднем и не хуже него в худшем случае.

в работе Y. Cesari, Thesis (Univ. of Paris, 1968), page 37, показано, что при n = 7 не существует метода сортировки, при котором достигалась бы нижняя граница длины внешнего пути (62 368). (Используя результат упр. 22, этот факт можно доказать самостоятельно.) С другой стороны, в указанной работе построены процедуры, для которых достигается нижняя граница (34) при п = 9 или 10. Вообще же, задачу минимизации среднего числа сравнений решить гораздо сложнее, чем найти 5(п). Вполне даже возможно, что при некоторых п все методы, минимизирующие среднее число сравнений, в худшем случае требуют более S{n) сравнений.

УПРАЖНЕНИЯ

1. [20] Нарисуйте деревья сравнений для сортировки четырех элементов методами (а) бинарных вставок ; (Ь) простого двухпутевого слияния. Каковы длины внешних путей для этих деревьев?

2. [М24] Докажите, что В{п) < L{n), и найдите все значения п, при которых имеет место равенство.

3. [М22] Если допускаются равные ключи, то при сортировке трех элементов возможны 13 исходов:

Ki=K2= Кз, Ki=K2< Кз, К1 = Кз< К2, К2 = Кз<К1, К1<К2 = Кз, К2<К1=Кз, Кз<К1= К2, Ki<K2< Кз, К1<Кз< К2, К2<К1<Кз, К2<Кз<К1, Кз<К1<К2, Кз<К2<К1.

Обозначим через Р„ число возможных исходов при сортировке п элементов, если допускаются равные ключи, так что (Ро, Pi, Р2, Рз, Р4, Ps, ) = (1, 1, 3, 13, 75, 541,...). Докажите, что производящая функция P{z) = Yl,„>o PnZ/nl равна 1/(2 - е). Указание. Покажите, что

Рп = ()Рп-* прип>0.

*:>0

4. [НМ27] (О. А. Гросс (О. А. Gross).) Найдите асимптотическое выражение для чисел Р„ из упр. 3 при п -> оо. [Указание. Рассмотрите разложение cot z на элементарные дроби.]

5. [16] Если допускаются равные ключи, то каждое сравнение может иметь не два, а три результата: Ki < Kj, Ki = Kj, Ki > Kj. В этом общем случае алгоритмы сортировки можно представлять в виде расширенных тернарных деревьев, в которых каждый внутренний узел i:j имеет три поддерева (левое, среднее и правое), соответствующие трем возможным исходам сравнения.

Нарисуйте расширенное тернарное дерево, определяющее алгоритм сортировки для п = 3, если допускаются равные ключи. В вашем дереве должно быть 13 внешних узлов, соответствующих 13 возможным исходам, перечисленным в упр. 3.

► 6. [М22] Пусть S{n) - минимальное число сравнений, необходимое для сортировки п элементов и выявления всех равенств между ключами, если каждое сравнение имеет три возможных результата, как в упр. 5. Нетрудно обобщить "теоретико-информационные" аргументы, приведенные в тексте раздела, и показать, что S{n) > [log3Pnl, где Рп - функция, проанализированная в упр. 3 и 4; докажите, что на самом деле S{n) = S{n).

7. [20] Нарисуйте расширенное тернарное дерево, как в упр. 5, для сортировки четырех элементов, если известно, что все ключи равны либо О, либо 1. (Так, например, если Ki < К2 к Кз < Ki, то понятно, что Ki - Кз п К2 = К}.) Добейтесь минимального числа сравнений в среднем, считая, что все 2 возможных исходных массивов равновероятны.

Обратите внимание на то, что должны быть проанализированы все имеющиеся варианты равенств; например, не прекращайте сортировку, если становится известно, что Ki < К2 < Кз < Ki.

8. [26] Нарисуйте расширенное тернарное дерево, как в упр. 7, для сортировки четырех элементов, если известно, что ключи - это либо -1, либо О, либо +1. Добейтесь минимального числа сравнений в среднем, считая, что все 3 возможных исходных массивов равновероятны.

9. [М20] Каково минимальное число сравнений в наихудшем случае при сортировке п элементов, как в упр. 7, когда известно, что все элементы равны либо О, либо 1?

► 10. [М25] Каково минимальное среднее число сравнений при сортировке п элементов, как в упр. 7, когда известно, что все ключи равны либо О, либо 1? Результат представьте в виде функции от п.

11. [НМ27] Пусть Sm{n) - минимальное число сравнений, необходимое в наихудшем случае для сортировки п элементов, как в упр. 5, причем известно, что вее ключи принадлежат множеству {1, 2,... ,т}. [Таким образом, согласно упр. 6 Sn{n) = S{n).] Докажите, что Sm{n) приближается к nlgm + 0(1) при фиксированном m и п -> оо.

► 12. [М25] (У. Г. Бурисиус (W. G. Bouricius), ок. 1954 г.) Предположим, что равные ключи могут встречаться, но наша цель - рассортировать элементы {Ki,K2,... ,Кп} таким образом, чтобы сформировать перестановку ai аг ... an, удовлетворяющую условию Kai < Ка2 • Ка,,; нам не важно, имеет ли место равенство между элементами Ка и Ка.

Будем говорить, что дерево сравнений сильно сортирует последовательность ключей, если оно сортирует ее в вышеуказанном смысле, независимо от того, какой путь выбран в узлах для которых Ki = Kj. (Дерево бинарное, а не тернарное.)

a) Докажите, что дерево, не содержащее избыточных сравнений, сильно сортирует любую последовательность ключей тогда и только тогда, когда оно сортирует любую последовательность различных ключей.

b) Докажите, что дерево сравнений сильно сортирует любую последовательность ключей тогда и только тогда, когда оно сильно сортирует любую последовательность нулей и единиц.

13. [М25] Докажите утверждение (17).

14. [М24] Выразите сумму (19) в замкнутом виде.

15. [M2i] Определите асимптотическое поведение функций В{п) и F{n) с точностью до O(logn). [Указание. Покажите, что в обоих случаях коэффициент при п содержит функцию, изображенную на рис. 37.)

16. [НМ26] (Ф. Хванг (F. Hwang) и Шень Линь (S. Lin).) Докажите, что при п > 22 выполняется неравенство F{n) > [Ign!].

17. [М20] Докажите тождество (29).

18. [20] Предположим, что процедура, начало которой изображено на рис. 36, породила граф............с эффективностью 12!/2. Доказывает ли это, что

5(12) = 29?

19. [40] Проведите эксперименты со следующим эвристическим правилом принятия решения, какую пару ключей сравнивать следующей при конструировании дерева сравнений. Пусть на каждой стадии сортировки ключей {Ki,... ,Кп} число ключей, о которых на основании выполненных до сих пор сравнений известно, что они < Ki, обозначается через щ, а число ключей, о которых известно, что они > К,, обозначается через vt, 1 < i < п. Перенумеруем ключи так, чтобы последовательность Ui/v, стала возрастающей: ui/vi < U2/V2 < < Un/vn. Теперь сравним Ki.Ki+i, где i - индекс, минимизирующий