Время выполнения этой программы можно оценить при помощи методов, которыми мы уже не раз пользовались (см. упр. 13 и 14). В среднем оно равно приблизительно (lOTVlgTV + 4.927V) машинных циклов с небольшим стандартным отклонением порядка y/N. В упр. 15 показано, что за счет некоторого удлинения программы можно сократить время примерно до 9NlgN.

Итак, в случае внутреннего слияния связное распределение памяти имеет бесспорные преимущества перед последовательным распределением: требуется меньше памяти и программа работает на 10-20% быстрее. Аналогичные алгоритмы опубликованы в работах L. J. Woodrum, IBM Systems J. 8 (1969), 189-203, и A. D. Woodall, Сотр. J. 13 (1970), 110-111.

УПРАЖНЕНИЯ

1. [21] Обобщите алгоритм М для к-путевого слияния исходных массивов хц < •• < Ximi при i = 1,2,... ,к.

2. [М24 ] Считая, что все С,") возможных расположений т элементов х среди п элементов у равновероятны, найдите математическое ожидание и стандартное отклонение числа выполнений шага М2 в алгоритме М. Чему рс1вны максимальное и минимальное значения этой величины?

> 3. [20] (Обиовлеиие.) Даны записи iZi,Дм и iZiД, ключи которых различны и упорядочены, т. е. < • < Км а К[ < • < К. Как нужно изменить алгоритм М, чтобы в результате слияния получался массив, в котором отсутствуют записи Ri первого массива, если во втором массиве также есть запись с таким же ключом?

4. [21] В основном тексте раздела отмечено, что сортировку методом слияния можно рассматривать как обобщение сортировки методом вставок. Покажите, что метод слияний имеет непосредственное отношение и к выбору из дерева (воспользуйтесь в качестве иллюстрации рис. 23).

> 5. [21] Докажите, что переменные i и j, используемые при выполнении шагов N6 и N10, не могут быть равны. (Поэтому на данных шагах проверка на случай возможного перехода к N13 необязательна.)

6. [22] Найдите такую перестановку К\ К ... Ki& множества {1,2,..., 16}, что

К2Ж3, КаЖь, Кб>К7, Ks>K9, Kio<Kn, Ki2<Ki3, КцККц,

которая, тем не менее, будет рассортирована при помощи алгоритма N всего за два про-, смотра. (Так как в искомой перестановке имеется не менее восьми серий, можно было бы ожидать, что после первого просмотра останется по меньшей мере четыре серии, после второго просмотра - две серии и сортировка, как правило, не завершится раньше третьего просмотра. Как можно обойтись всего двумя просмотрами?)

7. [16] Найдите точную формулу, выражающую число проходов алгоритма S в виде функции от N.

8. [22] Предполагается, что во время выполнения алгоритма переменные q а г представляют длины неслитых частей серий, обрабатываемых в данный момент; в начале работы как q, так и г устанавливаются равными р, в то время как серии не всегда имеют такую длину. Почему же алгоритм, тем не менее, работает правильно?

9. [24] Напишите MIX-программу для алгоритма S. Выразите частоту выполнения каждой команды через параметры, подобные А, В, В", С,... в программе L.

10. [25] (Д. А. Белл (D. А. Bell).) Покажите, что простое двухпутевое слияние массивов с последовательно расположенными элементами можно выполнить, имея всего Л/ ячеек памяти, а не 2N, как в алгоритме S.

11. [21] Является ли алгоритм L алгоритмом устойчивой сортировки?

► 12. [22] Измените шаг L1 алгоритма L так, чтобы двухпутевое слияние стало "естественным" используя наличие восходящих серий в исходном массиве. (В частности, если исходные данные уже упорядочены, то на шаге L2 можно завершить выполнение алгоритма сразу же после выполнения нового варианта шага L1.)

13. [М34] Проанализируйте среднее время работы программы L так, как были проанализированы другие алгоритмы в этой главе. Дайте толкование параметрам А, В, В,... и объясните, как вычислить их точные средние значения. Сколько времени затратит программа L на сортировку 16 чисел в табл. 3?

14. [М24] Пусть двоичное представление числа N есть 2 + 2 Н-----h 2", где ei > ег >

• • > et > О, t > 1. Докажите, что максимальное число сравнений ключей, выполняемых алгоритмом L, равно 1 - 2 -f Ylli {ек + к - 1)2*.

15. [20] Если промоделировать вручную работу алгоритма L, то обнаружится, что в нем иногда выполняются лишние операции. Примерно в половине случаев не нужны присваивания Ls <- р, [Ls] <- q на шагах L4 и L6, поскольку мы имеем Ls = р (или q) всякий раз, когда возвращаемся из шага L4 (или L6) к шагу L3. Как улучшить программу L и избавиться от этих лишних присваиваний?

16. [28] Разработайте алгоритм слияния списков, подобный алгоритму L, но основанный на трехпутевом слиянии.

17. [20] (Дж. Мак-Карти (J. McCarthy).) Пусть двоичное представление числа N такое же, как в упр. 14, и предположим, что дано N записей, организованных в t упорядоченных подмассивов, имеющих размеры 2*, 2,..., 2 соответственно. Покажите, как можно сохранить такое состояние при добавлении {{N + 1)-й записи и Л/ <- Л/ -Ь 1. (Полученный алгоритм можно назвать оперативной сортировкой методом слияния.)

18. [40] (М. А. Кронрод.) Можно ли рассортировать массив из N записей, содержащий всего две серии,

Ki<-<Km и Km+i<--<Kn,

за 0{N) операций в оперативной памяти, используя лишь небольшой дополнительный участок, размер которого не зависит or М и N? (Все алгоритмы слияния, описанные в этом разделе, используют дополнительную память, размер которой пропорционален N.)

19. [26] Рассмотрим железнодорожную сортировочную станцию с п накопительными тупиками - аналогами стека. На рис. 31 показана такая станция при п = 5. Операции в сети путей подобного типа имеют некоторое отношение к алгоритмам сортировки с п проходами. В упр. с 2.2.1-2 по 2.2.1-5 была рассмотрена такого рода железнодорожная сеть с одним тупиком. Было показано, что если с правого конца поступает N вагонов, то слева

Рис. 31. Сеть железнодорожных путей с пятью тупиками.

может появиться сравнительно небольшое количество из N1 всевозможных перестановок этих вагонов.

Предположим, что в п-тупиковый разъезд справа заталкивается 2" вагонов. Докажите, что при помощи подходящей последовательности операций можно получить слева любую из 2"! всевозможных перестановок этих вагонов. (Каждый тупик достаточно велик, и при необходимости в него можно поместить все вагоны.)

20. [47] В обозначениях упр. 2.2.1-4 при помощи железнодорожной сети с п тупиками можно получить не более Од? перестановок N элементов. Следовательно, для получения всех N1 перестановок требуется не менее log Л/1/log адг а log4 Л/тупиков. В упр. 19 показано, что нужно не более [Ig N] тупиков. Какова истинная скорость роста необходимого Числа тупиков при N -> оо?

21. [23] (А. Дж. Смит (А. J. Smith).) Объясните, как можно обобщить алгоритм L, чтобы он не только выполнял сортировку, но и вычислял число инверсий в исходной перестановке.

22. [28] (Дж. К. Р. Барнет (J. К. R. Barnett).) Разработайте способ повышения скорости сортировки методом слияния для многословных ключей. (В упр. 5.2.2-30 рассматривается аналогичная проблема применительно к быстрой сортировке.)

23. [МЗО] В упр. 13 и 14 анализируется "восходящая", или итеративная, версия сортировки методом слияния, где параметр цены c{N) сортировки N элементов удовлетворяет рекуррентному соотношению

c(iV) = с(2*) + c(iV - 2*) + /(2*, ЛГ - 2*) при 2" < N < 2*+

и /(т, п) есть цена слияния т элементов с п. Проанализируйте "нисходящую" версию или рекуррентное соотношение нашодобие "разделяй и властвуй",

c{N) =c{\NI2-]) +c{[,NI2\) + f{\Nl2}, [N/2\) при ;V > 1,

которое имеет место при использовании рекуррентной программы сортировки.

5.2.5. Сортировка методом распределения

Рассмотрим теперь интересный класс методов сортировки, который, как показано в разделе 5.4.7, по своей сути является обратным слиянию. Читателям, знакомым с перфокарточным оборудованием, хорошо известна эффективная процедура, применяемая в машинах для сортировки карт задолго до появления электронных компьютеров. Ту же идею можно использовать и для программирования компьютеров. Она общеизвестна под названиями "поразрядная сортировка", "карманная сортировка" (bucket sorting) и "цифровая сортировка" (digital sorting), поскольку базируется на анализе цифр ключей.

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

A<2<3<4<5<6<7<8<9<10<J<Q<K,