AOP_Tom3 (1021738), страница 55
Текст из файла (страница 55)
Эти идеи Уильямса и Флойда приводят к изящному алгоритму; который заслуживает пристального внимания (рис, 26). Алгоритм Н (Пирамидальнал сортировка). Записи Лы...,Лч перекомпоновываются в пределах того же фрагмента памяти; после завершения сортировки их ключи будут упорядочены следующим образом: Кг « Ква Сначала массив перестраивается в пирамиду, а затем вершина пирамиды многократно исключается и записывается на свое окончательное место. Предполагается, что Х > 2. Н1. [Начальная установка.] Установить 1 г — [1У/2] + 1, т < — Ю.
Н2. [Уменьшить 1 или т.] Если 1 > 1, установить 1 < — 1 — 1, Л < — Лг, К е- Кь (Если 1 > 1, значит, происходит преобразование исходного массива в пирамиду; если же 1 = 1, значит, ключи Кг Кг...К, уже образуют пирамиду.) В противном случае установить Л +- Л„К г — К„, Л„+- Лг и т < — т — 1; если в результате оказалось, что т = 1, установить Лг е- Л и завершить выполнение алгоритма. НЗ. [Приготовяться к "протаскиванию".] Установить у е-1. (К этому моменту К1г1з1 > Кг при 1 < [й/2] < й < т, (6) а запись Лг, т < й < Х, занимает свое окончательное место.
Шаги НЗ-Н8 называются алгаритлмом "прагааскиаанил"; выполняемые при этом операции эквивалентны установке Л~ < — Л с последующей перекомпоновкой записей Ль, .., Л„ таким образом, чтобы условие (6) выполнялось и при 1 = [й/2].) Н4. [Продвинуться вниз.] Установить 1 < — у и у е- 21 (На последующих шагах 1 = [у/2].) Если г' < т, перейти к шагу Н5; если 1 = т, перейти к шагу Нб; если же у > т, перейти к шагу Н8. Н5.
[Найти большего потомка.] Если К, < К г~ы то установить г'+- у'+ 1. Н6. [Больше, чем К?] Если К > К,, перейти к шагу Н8. НТ. !Поднять его вверх.) Установить Л; ь — Л и возвратиться к шагу Н4. Н8. [Занести Л.] Установить Л, ! — Л. (На этом алгоритм "протаскивание", начатый на шаге НЗ, заканчивается.) Возвратиться к шагу Н2.
1 Пирамидальную сортировку иногда описывают как рьвлгоритм. Это обозначение указывает на характер изменения переменных ! и г. Верхний треугольник соответствует фазе построения пирамиды, когда г = !У, а ! убывает до 1; нижний треугольник представляет фазу выбора, когда ! = 1, а г убывает до 1, В табл. 2 показана пирамидальная сортировка все тех же 16 чисел.
(В каждой строке изображено состояние в начале шага Н2, скобки указывают на значения переменных ! и г.) Я, е — Ль г+- г — 1. Перейти к шагу НЗ, если г > 1 Я~+-Л. 1 Эта программа приблизительно лишь вдвое длиннее программы Я, но при больших 1У она гораздо более эффективна. Время выполнения программы зависит от следующих параметров; Программа Н (Пирамидальнал соргпироека).
Записи, находящиеся в ячейках от 1МРРТ+1 по 1ИРРТ+М, сортируются при помощи алгоритма Н. В регистрах записана следующая информация; г11 т— з ! — 1, г12 = г — 1, г13 = 1, г14 = 1, г15— : г — 1, гА:— К ш Л, гХ ьз Л1. 01 ЗТАНТ ЕИТ1 И/2 1 Н1. Начальная ганоека. ! +- 11т/2) + 1. 08 ЕИТ2 М-1 1 г+-Х 08 1Н РЕС1 1 (!У/2) 1 < — ! — 1. 04 1.0А 1ИРРТ+1, 1 (АГ/2) Я +- Л~, К < — Кь 05 ЗН ЕИТ4 1,1 Р НЗ. П иготоеиться к "и таскиванию". 1< — ! Об ЕИТ5 0,2 Р 07 РЕСВ 0,1 Р г15 < — г — 1. 08 1МР 4Р Р Перейти к игагу Н4, 00 ВН 1.0Х 1ИРРТ,4 В + А — В Н5. Найти большего потомка. 10 СИРХ 1ИРОТ+1,4 В+ А — Р 11 1СЕ бр В+ А — В Переход, если К, > Ктьь 18 1ИС4 1 С В противном случае установить 1 +-1+ 1.
18 РЕСВ 1 С 14 9Н 101 1ИРРТ,4 С+ П гХ <- Я,. 15 ВН СИРА 1ИРВТ,4 В+ А Нб. Больше чем Ку 1б ЖЕ 8Р В+ А Перейти к шагу Н8, если К > К . 17 7Н ВТХ 1ИРРТ,З В Н7. По нять его еее х. АИ +- Ну. 18 4Н ЕИТЗ 0,4 В+ Р Н4. П о вин ться вниз. 1+-1. 10 РЕСБ 0,4 В + Р г15 +- г15 — 1'. ЙО 1ИС4 0,4 В + Р 1 +- 1'+ 1. 81 1ЬР 5В В+ Р Перейти к шагу Н5, если 1 С г. ЯЯ 162 9 Р— А+ Р Перейти к шагу Нб, если 1 = г.
88 8Н ЯТА 1МРРТ, 3 Р Нб. Занести Л. АИ +- Л. 2Н 11Р 18 Р Н2. Уменьшить ! нлн г. 88 !.РА 1МРРТ+1,2 5! — 1 Если ! = 1, установить Я+- Л„, К ь- К,. йб 1.РХ 1МРРТ+1 К вЂ” 1 87 ЗТХ 1ИРОТ+1, 2 5/ — 1 88 РЕС2 1 !У вЂ” 1 80 12Р ЗВ !У вЂ” 1 80 ВТА 1ИРРТл1 1 Р = !У + (!11/2) — 2 — число проходов с "протаскиванием"; А — число "протаскиваний", при которых ключ К, в конце концов, попадает во внутренний узел пирамиды;  — суммарное число ключей, просмотренных во время 'протаскиваний'; С вЂ” число присваиваний 7' е- 7' + 1 на шаге Н5; Р— число случаев, когда у = г на шаге Н4.
Эти параметры проанализированы ниже: как показывают эксперименты, они лишь незначительно отклоняются от средних значений: А 0.349К, В = 1Ч18)У вЂ” 1.87Х, С - 1эЮ!8Х вЂ” 0.94У, Р ш !пХ. (7) Прн !У = 1000, например, четыре эксперимента со случайными исходными данными показали соответствешю результаты А = 371, 351, 341, 340, В = 8055, 8072, 8094., 8108, С = 4056, 4087, .4017. 4083 и Р = 12, 14, 8, 13.
Общее время выполнения программы 7А + 14В + 4С + 20% — 2Р + 15(Х/2) — 28 равно, таким образом, в среднем примерно 16У!8К + 0.01Х машинных циклов. Глядя на табл. 2, трудно поверить в то, что пирамидальная сортировка так уж эффективна: болыпие ключи перемещаются влево, прежде чем мы успеваем отложить их вправо! Это и в самом деле странный способ сортировки прн малых Ю. Время сортировки 16 ключей из табл. 2 равно 1068и, тогда как при обычным методе простых вставок (программа 5.2.18) требуется всего 514и. Сортировка посредством простого выбора (программа 8) отнимает 853и. При больших К программа Н более эффективна. Напрашивается сравнение с сортировкой методом Шелла с убывающим смещением (программа 5.2АП) и быстрой сортировкой Хоара (программа 5.2.2Я), так как во всех трех программах сортировка выполняется путем сравнения ключей, причем требуется довольно малый объем дополнительной памяти или она не используется вовсе.
При 7г' = 1000 значения среднего времени выполнения равны приблизительно 160000и для пирамидальной сортировки, 130000и для сортировки методом Шелла, 80000п для быстрой сортировки. (И1Х вЂ” типичный представитель большинства компьютеров, но, разумеется, на конкретных машинах получатся несколько иные относительные величины.) С ростом 1У пирамидальная сортировка превзойдет по скорости метод Шелла, но асимптотическое выражение для времени выполнения 16%!8К - 23.08Х!пК никогда не станет лучше выражения для быстрой сортировки 11.67У!пХ.
Модификация пирамидальной сортировки, которая будет проанализирована в упр. 18, ускорит процесс вследствие снижения числа сравнений, но даже с этим усовершенствованием пирамидальная сортировка проигрывает по сравнению с быстрой сортировкой. С другой стороны, быстрая сортировка эффективна лишь в среднем; в наихудшем случае ее время работы пропорционально Кз. Пирамидальная же сортировка обладает тем интересным свойством, что для нее наихудший случай не намного хуже среднего. Всегда выполняются неравенства А < 15>У, В < Х!18>У), С < Х!!8>>). (8) Таким образом, независимо от распределения исходных данных выполнение программы Н не займет более 18>>>!!8>>'! + 38>У машинных циклов.
Пирамидальная сортировка — первый из рассмотренных нами до сих пор методов сортировки, время работы которого заведомо имеет порядок >>>!о8>У. Сортировка посредством слияний. которая будет обсуждаться ниже, в разделе 5.2.4, тоже обладает таким свойством, но эи>т метод требует больше памяти. Наибольший из включенных первым исключается. В главе 2 было показано, что линейные списки часто целесообразно классифицировать по характеру выполнения операций включения и исключения. Стек ведет себя по принципу "последним пришел — первым вышел" в том смысле, что при каждом исключении удаляется самый младший элемент списка (элемент, который был вставлен позже всех других элементов, присутствующих в данный момент в списке).
Простая очередь ведет себя по принципу "первым пришел — первым вышел" в том смысле, что нри каждом исключении удаляется самый старший из имеющихся элементов. В более сложных ситуациях, в таких как пример с моделированием лифта из раздела 2.2.5> необходим список наподобие "наименьший из включенных первым исключается", в котором при каждом исключении удаляется элемент, имеющий наименьший ключ. Такой список можно назвать приор»п>етной очередью, поскольку ключ каждого элемента отражает его относительную способность быстро покидать список. Сортировка посредством выбора — частный случай приоритетной очереди, над которой производится сначала >у операций вставки, а затем >>' операций удаления. Приоритетные очереди возникают в самых разнообразных приложениях.
Например, в некоторых численных итеративных схемах повторяется выбор элемента, имеющего наибольшее (или наименьшее) значение некоторого проверяемого критерия. Параметры выбранного элемента изменяются, и он снова встаю>яетгя в список с новым значением критерия, соответствующим новым значениям параметров. Приоритетные очереди часто используются в операционных системах при планировании заданий. Другие типичные применения приоритетных очередей упоминаются в упр. 15, 29 и 36; кроме того, много примеров будет приведено в следующих главах, Как же реализовать приоритетную очередь? Один из очевидных способов сделать это — организовать и поддерживать порядок по ключам в рассортированном списке элементов.
Тогда включение нового элемента, по существу, будет сведено к задаче, рассмотренной при изучении сортировки методом вставок в разделе 5.2.1. При друтом, еще более очевидном, способе работы с приоритетной очередью элементы в списке хранятся в произвольном порядке. Тогда для выбора нужного элемента приходится осуществлять поиск наибольшего (или наименьшего) ключа каждый раз, когда необходимо сделать исключение. В обоих этих очевидных подходах неприятность схютоит в том, что необходимо порядка П(>У) шагов для выполнения либо операции вставки, лиГ>о операции удаления, если в списке содержится >>' элементов, т.
е. при больших?У эти операции отнимают слишком много времени. В своей статье о пирамидальной сортировке Уильямс (Ж!!1!ап>э) обратил внимание на то, что пирамиды идеально подходят для приложений с большими приоритетными очередями, так как элемент можно вставить в пирамиду или удалить из нее за 0(!о8 >>>) шагов, К тому же все элементы пирамиды компактно располагаются в последовательных ячейках памяти. Фаза выбора в алгоритме Н вЂ” это последовательность шагов удаления в процессе наподобие наибольший иэ включенных первым исключаеглсл: чтобы исключить наибольший элемент Кы удаляем его и "протаскиваем" элемент Кк в новой пирамиде из Х вЂ” 1 элементов. (Если нужен алгоритм "наименьший из включенных первым исключается", как в примере с лифтом, то, очевидно, можно изменить определение пирамиды, заменив в (3) знак ">" знаком "<'! Для удобства будем рассматривать здесь лишь случай "наибольший из включенных первым исключается".) Вообще, если требуется исключить наибольший элемент, а затем вставить новый элемент х, можно выполнить процедуру "протаскивания'" при 1 = 1, г = Х и К = х.
Если же необходимо вставить элемент без предварительного исключения, можно воспользоваться "восходящей" процедурой из упр. 16. (9) (10) (11) КЕУ(Р) > КЕУ(ЕЕРТ(Р) ), КЕУ(Р) > КЕТ(й1СНТ(Р) ); Р13Т(Р) = 1 + ппп(0137(АЛЕЕТ(Р)),0131(Н1СНТ(Р))); 013Т(1.ЕРТ(Р)) > 013Т(Н1СНТ(Р)). Соотношение (9) аналогично условию существования пирамиды (3) и служит гарантией того, что в корне дерева находится наибольший ключ, а соотношение (10)— это просто определение поля 013Т, сформулированное выше. Соотношение (11) представляет собой интересное новшество: из него следует, что кратчайший путь к конечному узлу всегда можно получить, двигаясь вправо.