AOP_Tom3 (1021738), страница 61
Текст из файла (страница 61)
Чему равны максимальное и минимальное значения этой величины? 3. ]20] (Обваелеине.) Даны записи Вм..., Вм и В],..., В~в, ключи которых различны и упорядочены, т, е, Л~ < < Км и К', < . < К,'~. Как нужно изменить алгоритм М, чтобы в результате слияния получался массив, в котором отсугвствуют записи Вл первого массива, если во втором массиве также есть запись с таким же ключом? 4. ]2?] В основном тексте раздела отмечено, что сортировку методом слияния можно рассматривать как обобщение сортировки методом вставок.
Покажите, что метод слияний имеет непосредственное отношение и к выбору из дерева (воспользуйтесь в качестве иллюстрации рис. 23). б. (21] Докажите, что переменные г и зй используемые при выполнении шагов Нб и Х10, не могут быть равны. (Поэтому на данных шагах проверка на случай возможного перехода к Х13 необязательна.) б. ]22] Найдите такую перестановку Кз Кз... Кзг множества (1, 2,..., 16), что Кз > Кз, Кг > Кз, Ка > Кг, Кз > Кз, К~а < К]ь К1г < Кгз, Кы < Ли, которая, тем не менее, будет рассортирована при помощи алгоритма Х всего за два про-, смотра.
(Так как в искомой перестановке имеется не менее восьми серий, можно было бы ожидать, что после первого просмотра останется по меньшей мере четыре серии, после второго просмотра — две серии и сортировка, как правило, не завершится раньяге третьего просмотра. Как можно обойтись всего двумя просмотрами?) ЭУ 40 41 42 4Э 12 44 45 бб 47 ЕБ82 0,2 32Б2 ЕЗО БТ1 1ВРБТ,З(АВВЕ) БТ2 18РОТ,4(АВВЕ) ЕБТЗ 0 ЕЙ?4 ?э+1 1.01 18РРТ(1.) ЕР2 1?зРОТ+?э+1(Е) 3282 130 В у+ у. В Перейти к шагу ЬЗ, если д ф О. А ]Ь,]+- р. А ]Гг] +- О. А+ 1 12. Начать новый и осмот . з г — О. А+1 г+-?у+1. А+1 р+- Ь,. А+ 1 д+- Ьь А+ 1 Перейти к шагу ЬЗ, если д ф О.
Т. [10] Найдите точную формулу, выражающую число проходов алгоритма б в виде функции от АГ. 9. [22) Предполагается, что во время выполнения алгоритма переменные д и г представляют длины неслитых частей серий, обрабатываемых в данный момент; в начале работы как 0, так и г устанавливаютси равными р, в то время как серии не всегда имеют такую длину.
Почему же алгоритм, тем пе менее, работает правильно? 9. [24) Напишите И12-программу для алгоритма б. Выразите частоту выполнения каждой команды через параметры, подобные А, В, В, С,... в программе Ь. 10. [25) (Д. А. Белл (П. А. Вей),) Покажите, что простое двухпутевое слияние массивов с последовательно расположенными элементами можно выполнить, имея всего з А? ячеек памяти, а не 20?, как в алгоритме 3. 11. [21) Является ли алгоритм Ь алгоритмом устойчивой сортировки? ь 12. [22) Измените шаг 1 1 алгоритма Ь так, чтобы двухпутевое слияние стало "естественным", используя наличие восходящих серий в исходном массиве. (В частности, если исходные данные уже упорядочены, то на шаге Ь2 можно завершить выполнение алгоритма сразу же после выполнения нового варианта шага ЬЬ) ь 13. [А?04) Проанализируйте среднее время работы программы Ь так, как были проанализированы другие алгоритмы в этой главе.
Дайте толкование параметрам А, В, В',... и объясните, как вычислить их точные средние значения. Сколько времени затратит программа Ь на сортировку 16 чисел в табл. 3" 14. [ЛЩ) Пусть двоичное представление числа А? есть 2" + 2" + + 2", где г1 > ез > . > е~ > 9, 1 > 1. Докажите, что максимальное число сравнений ключей, выполняемых алгоритмом 1, равно 1 — 2" + ~,~~,(е + 1' — 1)2'". 15.
[20) Если промоделировать вручную работу алгоритма Ь, то обнаружится, что в нем иногда выполняются лишние операции. Примерно в половине случаев ие нужны присваивания [Ь,[ +- р, [Ь,[ +- д на шагах 14 и Ьб, поскольку мы имеем Ь, = р (или д) всякий рвз, когда возвращаемся из шага Ь4 (или Ьб) к шагу Ь3. Как улучшить програмиу Ь и избавиться от этих лишних присваиваний? 16. [20) Разработайте атгоритм слияния списков, подобный алгоритму Ь, но основанный на трехпутевом слиянии. 17.
[20) (Дж. Мак-Карти (Л. МсСагг?гу).) Пусть двоичное представление числа Х такое же, как в упр. 14, и предположим, что дано Аг записей, организованных в Г упорядоченных подмассивов, имеющих размеры 2", 2'з,..., 2" соответственно. Покажите, как можно сохранить такое состояние при добавлении ((Х+ 1)-й записи и А? +- Х+ 1. (Полученный алгоритм можно назвать ояераглненой сершироекой методом слияния.) 18.
[40) (М. А Кронрод.) Можно ли раггортировать масгив нз Ж записей, содержащий всего две серии, К| <. < Км и Кхге1( <Кя, за 0(А?) операций в оперативной памяти, используя лишь небольшой донолнншельнмй учасшок, размер которого не зависит от М и № (Все алгоритмы слияния, описанные в этом разделе, используют дополнительную память, размер которой пропорционален Ж.) 19. [2б) Рассмотрим железнодорожную сортировочную станцию с и накопительными тупиками — аналогами стека. На рис. 31 показана такая станция при и = 5. Операции в сети путей подобного типа имеют некоторое отношение к алгоритмам сортировки с и проходами В упр. с 2.2.1-2 по 2.2.1 — 5 была рассмотрена такого рода железнодорожная сеть с одним тупиком.
Было показано, что если с правого конца поступает Ю вагонов, то слева Рис. 31. Сеть железнодорожных путей с пятью тупиками. может появиться сравнительно небольшое количество иэ Х! всевозможных перестановок этих вагонов. Предположим, что в и-тупиковый разъезд справа заталкивается 2" вагонов. Докажите, что при помощи подходящей последовательности операций можно получить слева любую из 2"! всевозможных перестановок этих вагонов. (Каждый тупик достаточно велик, и при необходимости в него можно поместить все вагоны.) 20. [47) В обозначениях упр.
2.2.1 — 4 при помощи железнодорожной сети с п тупиками можно получить не более о,й перестановок Х элементов. Следовательно, для получения всех Х! перестановок требуется не менее !об АГ!/!ой ая !о34 Аг тупиков. В упр. 19 показано, что нужно не более [!3 Аг[ тупиков. Какова истинная скорость роста необходимого чиста тупиков при Х -+ оо7 21. [ЙЯ) (А. Дж.
Смит (А. Л. Бш!1)г).) Объясните, как можно обобщить алгоритм Ь, чтобы он не только выполнял сортировку, но и вычислял число инверсий в исходной перестановке. 22. [23[ (Дж. К. Р. Барнет (Л. К. К. Вагпесс).) Разработайте способ повышения скорости сортировки методом слияния для многословных ключей. (В упр. 5.2.2 — 30 рассматривается аналогичная проблема применительно к быстрой сортировке.) 23. [МЯО] В упр.
13 и 14 анализируется "восходящая", или итеративная, версия сортировки методом слияния, где параметр цены с(Х) сортировки Ю элементов удовлетворяет рекуррентному соотношению с(Х) = с(2 ) + с(г7 — 2 ) + /(2, !Ц вЂ” 2 ) при 2" < Х ( 2 +' и /(т, и) есть цена слияния ш элементов с и. Проанализируйте "нисходящую" версию или рекуррентное соотношение наподобие "разделяй н властвуй", с(Ж) = с( [Х/2)) + с([дг/2) ) + /([!7/2), [!7/2)) при Аг > 1, которое имеет место при использовании рекуррентной программы сортировки. 5.2.5.
Сортировка методом распределения Рассмотрим теперь интересный класс методов сортировки, который„как показано в разделе 5.4.7, по своей сути является обратимым слиянию. Читателям, знакомым с перфокарточным оборудованием, хорошо известна эффективная процедура, применяемая в машинах для сортировки карт задолго до появления электронных компьютеров.
Ту же идею можно использовать и для программирования компьютеров. Она общеизвестна под названиями "поразрядная сортировка'! "карманная сортировка" (Ьпс(сес эогс!пк) и "цифровая сортировка" (б!3)са) вот!(пб), поскольку базируется на анализе цифр ключей. Предположим, необходимо рассортировать колоду из 52 игральных карт. Определим упорядочение по старшинству (достоинству) карт в масти А < 2 < 3 < 4 ( б < б ( 7 < 8 < 9 < 10 < Л < Ц < К, а также по масти а<()< 2<й. Одна карта предшествует другой, если либо (~) она младше по масти, либо (й) масти обеих карт одинаковы, ио она младше по достоинству.
(Это частный случай лексикографического упорядоченна на множестве упорядоченных пар предметов; см. упр. 5 — 2.) Таким образом, получаем Ь Ф < 24Ь « " к 4Ь < Ь (> « ". 0 Ф < к йд. Можно было бы рассортировать карты одним из обсуждавшихся ранее методов. Люди, как правило, пользуются способом, по сути, аналогичным обменной поразрядной сортировке. Естественно рассортировывать карты сначала по мастям, разложив их в четыре стопки, а затем перекладывать карты внутри каждой стопки до тех пор, пока они не будут упорядочены по достоинству. Ио существует более быстрый способ! Сначала разложим карты в 13 стопок лицевой стороной вверх по их достоинству. После этого соберем все стопки вместе: снизу — тузы, затем — двойки, тройки и т. д.
и сверху — короли (лицевой стороной вверх). Далее перевернем колоду рубашками вверх и снова разложим ее, на этот раз в четыре стопки по масти, Сложив вместе полученные стопки так, чтобы внизу были трефы, затем бубны, черви и пики, получим упорядоченную колоду карт. Та же идея годится для сортировки числовых и буквенных данных. Почему же она работает — приводит к верному реэу.чьтату? Потому что (в нашем примере с игральными картами), если две карты при последнем раскладе попали в разные стопки, то онн имеют разные масти, так что карта с меньшей мастью младше.
Если же карты одной масти, они уже находятся в нужном порядке вследствие предварительной сортировки. Иначе говоря, при втором раскладе в каждой из четырех стопок карты будут расположены в порядке возрастания. Это рассуждение можно распространить на более общий случай и показать, что таким способом можно рассортировать любое множество с лексикографическим упорядочением (подробности приводятся в упр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
