AOP_Tom3 (1021738), страница 55

Файл №1021738 AOP_Tom3 (Полезная книжка в трёх томах) 55 страницаAOP_Tom3 (1021738) страница 552017-07-10СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 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) представляет собой интересное новшество: из него следует, что кратчайший путь к конечному узлу всегда можно получить, двигаясь вправо.

Характеристики

Тип файла
DJVU-файл
Размер
10,16 Mb
Тип материала
Высшее учебное заведение

Список файлов книги

Свежие статьи
Популярно сейчас
Зачем заказывать выполнение своего задания, если оно уже было выполнено много много раз? Его можно просто купить или даже скачать бесплатно на СтудИзбе. Найдите нужный учебный материал у нас!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6549
Авторов
на СтудИзбе
300
Средний доход
с одного платного файла
Обучение Подробнее