Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 40
Текст из файла (страница 40)
(На, последующих шагах ! = [у/2].) Если у < г, перейти к шагу Н5; если .~ = г, перейти к шагу Нб; если же э > г, перейти к шагу Н8. НЬ. [Найти большего потомка.] Если К! < К!ам то установить у +- у + 1. Нб. [Больше„чем КЗ] Если К > К, перейти к шагу Н8, Н7. (Поднять его вверх,) Установить Н; ь- Н/ и возвратиться к шагу Н4. НВ, [Занести Н.) Установить Н; ь- Н. (На этом алгоритм "протаскивания", начатый на шаге НЗ, заканчивается.) Возвратиться к шагу Н2. $ Пирамидальную сортировку иногда описывают как р)-алгоритм. Это обозначение указывает на характер изменения переменных 1 и г.
Верхний треугольник соответствует фазе построения пирамиды, когда г = /РР, а 1 убывает до 1; нижний треугольник представляет фазу выбора, когда1 = 1, а г убывает до 1. В табл, 2 показана пирамидальная сортировка все тех же 16 чисел. (В каждой строке изображено состояние в начале шага Н2, скобки указывают на значения переменных 1 и г,) Программа Н (Пирамидальная сортировка). Запвси, находящиеся в ячейках от 1ИРОТ+1 по 1ИРОТ+И, сортируются при помощи алгоритма Н. В регистрах записана следующая информация.
"г11 Рн 1 — 1, г12 ьз г — 1, г13 ги 1, г14 эз у, г15 = г — у', ГА гн К и Н, гХ ьз Ну, 01 ЗТАЯТ ЕИТ1 И/2 1 Н1, ачатьная теленка. 1+- (РРР/2) + 1. 08 ЕИТ2 И-1 1 г+- РРР. 08 1Н ОЕС1 1 (РРР/2) 1+- 1 — 1. 04 ЫА 1ИРОТ+1,1 (АР/2) В <- ВР, К <- КР. 08 ЗН ЕИТ4 1,1 Р . нготовнть к "л таскюРанню". у Р- б 00 ЕИТЗ 0,2 Р 07 ВЕСЗ 0,1 Р г15+- г -у, 08 ЛНР 4Р Р Перейтн к шагу Н4. ОУ ЗН ЬОХ 1ИРОТ,4 В+ А — В 5. Найтк большего и мка. 10 СИРХ 1ИРОТ+1„4 В+ А — В 11 ЛОЕ бР В+А — 17 Переход, если КР > Ктьь 18 1ИС4 1 С В противном случае установить у +- ) + 1.
18 ОЕСЗ 1 С 14 9Н 1,ОХ 1ИРОТ,4 С+ В гХ ~- Лу, И 6Н СИРА 1ИРОТ,4 В+А НО. Больше чем Ку 10 ОСЕ ЗР В+ А ПеРейти к шагУ НЗ, если К > КР. 17 7Н ЗТХ 1ИРОТ, 3 В 7. ять его вв х. ВР +- Ву. 18 4Н ЕИТЗ 0,4 В+ Р Н4. П внн ться вннэ. Р+-у. 1У ОЕСЗ 0,4 В+ Р г15 <- гЦ вЂ” 1. 80 1ИС4 0,4 В+ Р О < — 1+1. 81 ЛЗР ЗВ В+ Р Перейтн к шагу НЬ, если у < г. 88 552 9 Р— А+ 11 Перейти к шагу Нб, еслк у = г. РР РН РРР РРРРР.Р Р ьР РнвР а ЛР Л.
84 2Н 31Р 1В г. 86 1ОА 1ИРОТ+1,2 дг — 1 Если 1 = 1, установить В+- В,, К+- К„. 86 ЫХ 1ИРОТ+1 РРР— 1 87 ЗТХ 1ИРОТ+1,2 Ж вЂ” 1 88 ОЕС2 1 ДР-1 80 Л2Р ЗВ РР' — 1 80 ЗТА 1ИРОТ+1 1 Н, +- ВР. г ь- г — 1. Перейтн к шагу НЗ, если г > 1 ВР+-Н. $ Эта программа приблизительно лпшь вдвое длиннее программы 8, но при больших Рт' она гораздо более эффективна. Время выполнения программы зависит от следующих параметров: Р = й' + 1Ф/2) — 2 — число проходов с "протаскиванием",: А — число "протаскиваний", при которых ключ К, в кояце концов, попадает во внутренний узел пирамиды;  — суммарное число ключей, просмотренных во время "протаскиваний"; С вЂ” число присваиваний у' <- 7' + 1 на шаге Н5; Р— число случаев, когда у = г н» шаге Н4.
Эти параметры проанализированы ниже; как показывают эксперименты, они лишь незначительно отклоняются от средних значений: В - У18Л вЂ” 1.87У, Р 1пМ, А 0.349Ю, С ~1 Ю 18 57 — 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Р + 1517э/21 — 28 равно, таким образом, в среднем примерно 167г'18г7 + 0.01лГ машинных циклов. Глядя на табл. 2, трудно поверить в то, что пирамидальная сортировка так уж эффективна: большие ключи перемещаются влево, прежде чем мы успеваем отложить их вправо! Это и в самом деле странный способ сортировки при малых К. Время сортировки 16 ключей из табл. 2 равно 1068и, тогда как прн обычным методе простых вставок (программа 5.2.18) требуется всего 514и.
Сортировка посредством простого выбора (программа 8) отнимает 853п. При больших К программа Н более эффективна. Напрашивается сравнение с сортировкой методом Шелла с убывающим смещением (программа 5.2.10) и быстрой сортировкой Хоара (программа 5.2.2Я), так как во всех трех программах сортировка выполняется путем сравнения ключей, причем требуется довольно малый объем дополнительной памяти или она не используется вовсе. При Ю = 1000 значения среднего времени выполнения равны приблизительно 160000и для пирамидальной сортировки, 130000и для сортировки методом Шелла, 80000н для быстрой сортировки, (И1Х вЂ” типичный представитель большинства компьютеров, но, разумеется, на конкретных машинах получатся несколько иные относительные величины.) С ростом М пирамидальная сортировка превзойдет по скорости метод Шелла, но асимптотическое выражение для времени выполнения 16Ю!8Ж и 23.08Л!и К никогда не станет лучше выражения для быстрой сортировки 11.67йг!пЮ.
Модификация пирамидальной сортировки, которая будет проанализирована в упр. 18, ускорит процесс вследствие снижения числа сравнений, но даже с этим усовершенствованием пирамидальная сортировка проигрывает по сравнению с быстрой сортировкой. С другой стороны, быстрая сортировка эффективна лишь в среднем; в наихудшем случае ее время работы пропорционально Хэ. Пирамидальная же сортировка обладает тем интересным свойством, что для нее наихудший случай не намного хуже среднего. Всегда выполняются неравенства Л<1.5У, В«У(15У(, С<и!)5Ц.
(3) Таким образом, независимо от распределения исходных данных выполнение программы Н не займет более 18Ю(!5Ф) + 38Л машинных циклов. Пирамидальная сортировка — первый из рассмотренных нами до сих пор методов сортировки, время работы которого заведомо имеет порядок Х !ой Ж. Сортировка посредством слияний, которая будет обсуждаться нике, в разделе 5.2.4, тоже обладает таким свойством, но этот метод требует больше памяти, Наибольший из включенных первым исключается. В главе 2 было показана, что линейные списки часто целесообразно классифицировать по характеру выполнения операций включения и исключения. Сшек ведет себя по принципу "последним пришел — первым вышел" в том смысле, что при каждом исключении удаляется самый младший элемент списка (элемент, который был вставлен позже всех других элементов, присутствующих в данный момент в списке).
Простая очередь ведет себя по принципу "первым пришел — первым вышел" в том смысле, что при каждом исключении удаляется самый старший из имеющихся элементов. В более сложных ситуациях, в таких как пример с моделированием лифта из раздела 2.2.5, необходим список наподобие "наименьший из включенных первым исключается", в котором при каждом исключении удаляется элемент, имеющий наименьший ключ.
Такой список можно назвать приоритпетпо4 очередью, поскольку ключ каждого элемента отражает его относительную способность быстро покидать список. Сортировка посредством выбора — частный случай приоритетной очереди, над которой производится сначала Х операций вставки, а затем Х операций удаления. Приоритетные очереди возникают в самых разнообразных приложениях. Например, в некоторых численных итеративных схемах повторяется выбор элемента, имеющего наиболыпее (или наименьшее) значение некоторого проверяемого критерия. Параметры выбранного элемента изменяются, и он снова вставляется в список с новым значением критерия, соответствующим новым значениям параметров.
Приоритетные очереди часто используются в операционных системах при планировании заданий. Другие типичные применения приоритетных очередей упоминаются в упр. 15, 29 и 36; кроме того, много примеров будет приведено в следующих главах. Как же реализовать приоритетную очередь? Один из очевидных способов сделать это — организовать и поддерживать порядок по ключам в рассортированном списке элементов. Тогда включение нового элемента, по существу, будет сведено к задаче, рассмотренной при изучении сортировки методом вставок в разделе 5.2.1.
При другом, еще более очевидном, способе работы с приоритетной очередью элементы в списке хранятся в проимюльнам порядке. Тогда для выбора нужного элемента приходится осуществлять поиск наибольшего (или наименьшего) ключа каждый раз, когда необходимо сделать исключение. В обоих этих очевидных подходах неприятность состоит в том, что необходимо порядка Й(Ж) шагов для выполнения либо операции вставки, либо операции удаления, если в списке содержится Ж элементов, т.
е. при больших Ф эти операции отнимают слишком много времени. В своей статье о пирамцдальнай сортировке Уильямс (1т'!1!!ашэ) обратил внимание на то, что пирамиды идеальна подходят для приложений с большими приоритетными очередями, так как элемент можно вставить в пирамиду или удалить из нее за О(!ой Л) шагов. К тому же все элементы пирамиды компактно располагаются в последовательных ячейках памяти. Фаза выбора в алгоритме Н вЂ” это последова тельностыпагов удаления в процессе наподобие наибольший иэ включеннмт первым исключаешсл; чтобы исключить наибольший элемент Км удаляем его и "протаскиваем" элемент Ки в новой пирамиде из М вЂ” 1 элементов. (Если нужен алгоритм "наименьший из включенных первым исключается", как в примере с лифтом, то, очевидно, можно изменить определение пирамиды, заменив в (3) знак ">" знаком "<".
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
