Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 45
Текст из файла (страница 45)
Если р > О, вернуться к шагу 13. 15. [Завершить подсписок.] Установить Ь <- д, э <- б Далее установить 1 <- д и д <- Ья один или более рвз, пока не станет о < О, после чего перейти к шагу Ь8. Ьб. [Продвинутыу.] [Шаги 16 и Ь?двойствеины шагам 1.4 и 1Л.) Установить [.Ц +- й, э < — д, д +- Ь . Если у > О, вернуться к шагу 13. Ь?. [Завершить подсписок.] Установить Ь, +- р, э +- Ь Затем установить г +- р и р +- Х р один или более раз, пока не станет р < О. 18. [Конец просмотра?] (К этому моменту р < О и о < О, так как оба указателя продвинулись до конца соответствующих подсписков.) Установить р <- -р, д < — -д.
Если д = О, установить [Х,] +- р, [Х ~[ ~ — О и вернуться к шагу 12. В противном случае вернуться к шагу 13. $ Пример работы этого алгоритма приведен в табл. 3, в которой показаны связи к моменту выполнения шага 1 2. По окончании выполнении алгоритма можно, пользуясь методом нз упр. 5.2-12, перекомпоновать в памяти записи Вы..., Вм твк, чтобы нх ключи стали упорядоченными. Нужно отметить интересную аналогию между слиянием списков и сложением разреженных многочленов (см. алгоритм 2.2.4А). Напишем теперь И11-программу для алгоритма Ь, чтобы выяснить, столь ли выгодно оперировать списками с точки зрения скорости выполнения, как н с точки зрения расхода памяти? Программа Ь [Соргпировка посредсшвом слияния списков).
Для удобства предполагается, что записи занимают одно слово, причем Ьз хранится в поле [О: 2) и Таблица 3 СОРТИРОВКА ПОСРЕДСТВОМ СЛИЯНИЯ СПИСКОВ 1 2 3 4 5 б 7 8 9 10 11 12 !3 !4 15 16 17 !70 897 -8 -9 5 -11 8 5 8 5 8 5 908 -7 -10 -!3 0 0 275 653 -10 -!1 7 -13 7 О 1 14 !О 14 426 154 -12 -13 9 !2 12 10 !2 !О 1 6 509 612 677 765 -Н -15 -!6 О -16 !4 О 0 9 14 16 0 13 9 16 0 3 9 1б 7 703 0 2 15 4 15 6 !5 1! 15 0 512 061 -5 -6 — 8 3 -11 2 7 2 13 2 КХ 10 Хо 10 Ь1 503 087 -3 -4 -6 ! 3 3 6 12 11 1 2 4 4 4 1МРОТ + 1. Состояние регистров таково: 711 93 р, 1'т' > 2.
Опрелеление имен полей. ЬЬ П готовить а списка. Хн +- -(1+ 2). Ф вЂ” 2>4>0. Ха +- 1. Ьн+! +- 2. Хн !4 — О. Ьн с-О. Перейти к шагу 1,2, КХ вЂ” в поле (3; б) по алресу г(2 = д, г13 = в, г14 = Х, гА гб К 01 Ь ЕЦО 0'. 2 08 АВБЬ ЕЦО 1: 2 08 КЕУ ЕЦО 3:Я 04 ЯТАВТ ЕМТ1 М-2 06 ЕМКА 2,1 06 БТА 1МРОТ,1(Ь) 07 ОЕС1 1 08 11Р в-3 08 ЕМТА 1 10 БТА ХМРОТ(Ь) 11 ЕМТА 2 БТА 1МРОТ+В+1(Ь) 18 БТЕ 1МРОТ+М-1(Ь) 14 БТЕ 1МРОТ+М(Ь) 18 ХМР 1,2 16 ЬЗЦ ЬОА 1МРОТ,2 17 ЬЗР СИРА ТМРОТ,1(КЕУ) 18 3Ь Ьб 18 Ьд БТ1 ХМРОТ,З(АВЯ1.) 80 ЕМТЗ 0,1 81 1.01 1МРОТ, 1 (Ы 88 81Р ЬЗР 88 ЬБ БТ2 1МРОТ,З(Ь) 84 ЕМТЗ 0,4 Ад ЕМТ4 0,2 86 ЬО2 1МРОТ,2(1.) 87 32Р «"2 88 1МР ЬВ 88 Ьб БТ2 ХМРОТ,З(АВВЫ 80 ЕМТЗ 0,2 81 ЬО2 1МРОТ,2(Ь) 88 12Р ЬЗЦ 88 1,7 ЯТ1 1МРОТ,З(Ь) 84 ЕМТЗ 0,4 86 ЕМТ4 0,1 86 ЬО1 1МРОТ, 1 ПЫ 87 81Р 4-2 88 ЬВ ЕММ1 0,1 1 1д — 2 1д — 2 Ю вЂ” 2 1д — 2 1 1 1 1 1 1 1 С'+В С С С' СФ ~М С' ВР В' рХ р~ рФ В~ Св Сп Сп Сп В" Вп ХУ' Х!и В Перейти к шагу Ьб, если Лт < К„.
Н ввв а~ь В.~ Р в +" р. р 4- Х,ш Перейти к шагу ЬЗ, если р > О. Ьд. Заве шить п штнсок. Х, +- д. в+- !. С+- д. д+ ьт. Повторить, если д > О, Перейти к шагу ЬБ. Ьб. Пощвнндт д, !Ь,( +-д. в+- д. д+ Х! Перейти к шагу 1.3, если д > О. Ь7. 3 шить и список. Ь. +-р. в+- 1, 1+- р. р+- Ь Повторить, если р > О.
. Кон смет а7 р+- -р, уу ЕММ2 0,2 В я+- -я 40 32МЕ ЬЗО В Перейти к шагу 1.3, если я 1е О, 41 5Т1 1МРОТ,З(АВЗЬ) А (Е„! г- р. 42 ЗТЕ 1МРОТ,4(йВЗЬ) А )Е,! +- О. 43 Ьг ЕМТЗ 0 А+1 Ь2. Начатьловыйп осмо, з+-О. 44 ЕМТ4 М+1 А+ 1 г г- )г'+ 1. 43 Ь01 1МРОТ(Ь) А+1 рг- Х,- Аб Ь02 1МРОТ+М+1(Ь) А + 1 я г- Еь 47 32МЕ ЬЗО А+1 Перейти к шагу ЬЗ, если я ~ О. 3 Время выполнения этой программы можно оценить при помощи методов, которыми мы уже не раз пользовались (см.
упр. 13 и 14), В среднем оно равно приблизительно (10Ю !Е Х + 4.92Х) машинных циклов с небольшим стандартным отклонением порядэа тУЮ. В упр. 13 показано, что за счет некоторого удлинения программы можно сократить время примерно до 9)г' !Е Х. Итак, в случае внутреннего слияния связное распределение памяти имеет бесспорные преимущества перед последовательным распределением: требуется меньше памяти и программа работает на 10-20% быстрее.
Аналогичные алгоритмы опубликованы в работах Ь. 3, %оодпнп, 1ВМ Вув1егпэ Х 8 (1969), 189-203, и А. П. %ЪобаИ, Сошр. Х 13 (1970), 110-Ш. УПРАЖНЕНИЯ 1. (21) Обобщите алгоритм М для й-иушееоге слвлиел исходных массивов х,г « . хью при г = 1, 2,..., й. 2. (М24) Счигэв, что вге (и+") возможных расположений ш элементов х среди и элементов у равновероятны, найдите математическое ожидание и стандартное отклонение числа выполнений шага М2 в алгоритме М. Чему равны максимальное и минимальное значения этой величины? ° ' 3. (2д) (Обиоелсивс.) Даны записи Вп..., Вм и Вм..., В',„, ключи которых различны и упорядочены, т.
е. Кг « . Км и К, '« . Кк. Как нужно изменить алгоритм М, чтобы в результате слияния получался массив, в котором ошсутсшеуют записи В; первого массива, если во втором массиве также есть запись с таким же ключом? 4. (21) В основном тексте раздела отмечено, что сортировку методом слияния можно рассматривать как обобщение сортировки методом вставок. Покажите, что метод слияний имеет непосредственное отношение и к выбору иэ дерева (воспользуйтесь в качестве иллюстрации рис. 23). ° 6.
Щ Докажите, что переменные г и у, используемые при выполнении шагов !гб и В10, не могут быть равны. (Поэтому иа данных шагах проверка на случай возможного перехода к ?413 необязателыга.) б. (22) На?гните такую перестановку К~ Кг... Кы множества (1, 2,..., 16), что Кг > Кг, К4 > Кг, Ке > Кг, Ке > Кг, Кго < Кп, Кгг < Кш, 'гы < Кш, которая, тем не менее, будет рассортирована при помощи алгоритма Х всего за два про-.
смотра. (Так как в искомой перестановке имеется не менее восьми серий, можно было бы ожидать, что после первого просмотра останется по меньшей мере четыре серии, после второго просмотра — две серии и сортировка, как правило, не завершится раньше третьего просмотра. Как можно обойтись всего двумя просмотрами?) 7, [16] Найдите точную формулу, выражающую число проходов алгоритма 6 в виде фуикпди от Х. 8. [22] Предполагается, что во время выполнения алгоритма переменные о и г представляют длины неслитых частей серий, обрабатываемых в данный момент; в начале работы как о, так и г устанавливаются рааиыми р, в то время как серии ие всегда имеют такую длину. Почему же алгоритм, тем ие менее, работает правильно? 9.
[24] Напишите И11-программу для алгоритма Я. Выразите частоту выполнения каж- дой команды через параметры, подобные А, В', В", С',... в программе Ь, 10. [25] (Д. А, Белл (П. А. ВеИ).) Покажите, что простое двухпутевое слияние массивов с последовательно расположеиными элементами можно выполнить, имея всего 1Х ячеек памяти, а ие 2Х, как в алгоритме 6. 11. [21] Является ли ащоритм Ь алгоритмом устойчивой сортировкиу ь 12. [22] Измеиите шаг Ь1 алгоритма 1 так, чтобы двухпутевое слийиие стало "естествен- ным", используи ивличие восходящих серий в исходном массиве.
(В частности, если ис- ходные данные уже упорядочеиы, то иа шаге Ь2 можно завершить выполнение алгоритма сразу же после выполнения нового варианта шага ЬЬ) ь 13. [Муд] Проанализируйте среднее время работы программы 1 так, как были проана- лизированы другие алгоритмы в этой главе, Дайте толкование параметрам А, В, В',... и объясните, как вычислить их точные средние значения.
Сколько времени эатратит программа Ь иа сортировку 16 чисел в табл. 31 14. [М24] Пусть двоичное представление числа )Ь' есть 2" + 2'э + . + 2", где е1 > еэ > > е~ > О, 1 > !. Докажите, что максимальное число сравнений ключей, выполняемых алгоритмом 1, равио 1 — 2" + [" ~~, (сь + к — 1)2'". 16. [20] Если промоделировать вручную работу алгоритма Ь, то обиаруяснтся, что в нем иногда выполняются лишние операции.
Примерно в половине случаев ие нужны присваивания [1„[ е- р, [Е,[ э- д на шагах Ь4 и Ьб, поскольку мы имеем Ь„= р (или е) всякий раз, когда возвращаемся из шага 1А (или Ьб) к шагу Ь3. Как улучшить программу 1. и избавиться от этих лишних присваиваний? 16. [23] Разработайте алгоритм слияния списков, подобный алгоритму Ь, но основанный иа трехпутевом слиянии. 17. [20] (Дж.
Мак-Карти (3. МсСагспу).) Пусть двоичное представление числа Ю такое же, как в упр. 14, и предположим, что дано Х записей, организованных в 1 упорядочен- ных подмассивов, имеющих размеры 2",2",...,2"' соответственно. Покажите, как можно сохранить такое состояние при добавлении ((Ф + 1)-й записи и К +- )Ь'+ 1. (Полученный алгоритм можно пазвать оперативной сортировкой методом сяияипл.) 18.
[40] (М. А. Кронрод.) Можно ли рассортировать массив из Ф записей, содержащий всею две серии, К, « " Км Км+, « -" К„, за О(Х) операций в оперативной памяти, используя яшиь небояьшой допояиптеяьный учасшок, размер которого ие зависит от М и А'1 (Все алгоритмы слияния, описанные в этом раэделе, используют дополнительную память, размер которой пропорционален Х) 19. [26] Рассмотрим железнодорожную сортировочиую станцию с и накопительными тупиками — аналогами стека. На рис. 31 показана такая станция при и = о. Операции в сети путей подобного типа имеют некоторое отношение к алгоритмам сортировки с и проходами. В упр.
с 2.2.1-2 по 2.2.1-5 была рассмотрена такого рода железнодорожная сеть с одиим тупиком. Было показано, что есчи с правого конца поступает Х вагонов, то слева Рис. 31- Сеть железнодорожных путей с пятью тупиками. может появиться сравнительно небольшое количество из Х! всевозможных перестановок этих вагонов.
Предположим, что в я-тупиковый разъезд справа заталкивается 2" вагонов. Дока- жите, что прн помощи подходящей последовательности операций можно получить слева любую из 2"! всевозыожньш перестановок этих вагонов. (Каждый тупик достаточно велик, и прн необходимости э него можно поместить все вагоны.) 20, [47[ В обозначениях упр. 2.2.1-4 при помощи железнодорожной сети с и тупиками можно получить не более алэ перестановок Ф элементов. Следовательно, для получения всех Ф! перестановок требуется не менее !об йй/!ой ал ж !об А! тупиков. В упр.
19 нака- зано, что нужно не более [!й!7) тупиков. Какова истинная скорость роста необходимого числа туликов при А! -+ оо7 21. [ЯЯ) (А. Дж. Смит (А. Л. Вш!1Ь).) Объясните, как можно обобщить алгоритм 1, чтобы он не только выполнял сортировку, но и вычислял число инверсий в исходной перестановке. 22. [28) (Дж. К. Р. Барнет (Л. К. й. Вэгпем).) Разработайте способ повышения скорости сортировки методом слияния для многословных ключей.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
