Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 17
Текст из файла (страница 17)
2.7 и 2.8 являются пира' мидами, и, в частности, элемент Ь~ пирамиды является ее наименьшим элементом й~ = |п1П (61 ... 6„). Теперь предположим, что дана пирамида с элементами Ь|+ь ..., Ь, для некоторых значений ! и г н нужно добавить г. Сор и новый элемент х для того, чтобы сформировать расширенную пирамиду йь ..,, й,. Возьмем, например, исходную пирамиду Ьь ..., Ьт, показанную на рис.
2.7, и расширим эту пирамиду «влевоэ, добавив элемент й, = 44. Новый элемент х сначала помещается в вершину дерева, а затем «просеивается» по пути, па котором находятся меньшие по сравнению с ним элементы, которые одновременно поднимаются вверх; таким Рис. 2.6. Массив Ь, расположеииый в виде бииариого дерева, Рис. 2.7, Пирамида иа семи адемеитов. ББ Рис. 2.2. Просеиваиие иаизча 44 через пирамиду. образом формируется новая пирамида, В данном примере значение 44 сначала меняется местами с 06, затем с 12, и так формируется дерево, показанное на рнс. 2.8.
Далее мы процесс просеивания будем формулировать следующим образом: г', 1' — пара индексов, обозначающих элементы, которые нужно менять местами на каждом шаге просеивания. Мы предоставляем читателю возможность самому убедиться, что предложенный способ просеивания действительно позволяет сохранить условия (2.13), определязошие пирамиду. Изящный способ построения пирамиды зп зыи был предложен Р. У.
Флойдом. В нем используется следующая про. дд Сортировка массивов 98 цедура просеивания (программа 2.7), Дан массив Ль ..., 8„; ясно, что элементы й„та+~ ... 1с„уже образуют пирамиду, поскольку не существует двух индексов й 1, таких, что 1= 21 (или 1 = 21 + !), Эти элементы составляют последовательность, которую можно рассматривать как нижний ряд соответствующего двоичного дерева (см, рис.
2.6), где не тре- ргесеееге вф(1,т: 1игуех) ~ 1аЬе! 13; гвг 1,1': тйх; х: Иещ; Ьейй с:= 1; 1 ."= 2в1; х:= аЯ, иЫеу <, г йо Ьейй К1 < и йеп ЬТ аИ .йеу > аЦ+Ц .йеу йеи 1:= 1+1; 11 х .Ьеу к а~Я .йеу йеи ие1о 13; аИ:= а(Я„' 1:=11 1.= 2е((вф) евд; 13: а[11:= х Еяе Программа 2.7. Просеивание. буется никакого упорядочения. Теперь пирамида расширяется влево: на каждом шаге добавляется новый элемент и при помощи просеивания помещается на соответствующее место, Табаииа 8.6. Построение иирамидм 44 бб 1с ев ~ 94 18 Об 87 94 18 06 67 94 18 12 67 94 18 12 67 Этот процесс иллюстрируется табл.
2.6 и приводит к пирамиде, показанной на рис. 2.6. Следовательно. процесс построения пирамиды из и элементов (л з11и монсно описать следующим образом: 1:= (и йг 2) + 1; егЬйе! > 1 йе Ь йй1:-1 1;,(1)(1„) ми) 2. Сортировка 06 42 12 56 94 18 44 67 18 42 44 66 44 42 18 12 06 18 12 06 44 42 18 72 06 44 42 18 12 06 пирамиды, приведенной в табл, 2.7. Этот процесс описывается с помощью процедуры з)11 (программа 2.7) следующим образам: г:.= и; нй!1е г > ! аа Ьеят х: —.= а[1); а[Ц:=- а[г) а[г):.= х,' г: =. г — 1; х(7)(1,г) епй Из табл. 2.7 видно, что на самом деле в результате мы получаем последовательность в обратном порядке. Но это легко можно исправить, изменив направление отношения порядка в процедуре зф, В результате мы получаем процедуру Неарзаг), показанную в программе 2.8.
Анализ пирамидальной сортировки. С первого взгляда неочевидно, что этот метод сортировки дает хорошие результаты. Ведь элементы с большими ключами вначале просеиваются влево, прежде чем, наконец, окажутся справа. Действительно, эта процедура не рекомендуется для такого небольшого числа элементов, как, скажем, в пашем примере. Однако для больших и пирамидальная сортировка оказы. Для того чтобы рассортировать элементы, надо выполнить п шагов просеивання: после каждого шага очередной элемент берется с вершины пирамиды. Вновь встает вопрос, куда помещать элементы с вершины и возможна лн сортировка )п зди. Да, такое решение существует! На каждом шаге из пирамиды выбирается последняя компонента (скажем, х), верхний элемент пирамиды помещается иа освободившееся место х, а х просеивается на свое место.
В этом случае необходимо совершить и — 1 шагов, что показано на примере Тибдипа 2.7, Пример пирамидвльиой сортировии дх Сортировка массивов ргосеоаге йеаувогг; тат 1,г: !лс!ех! хи !гент; ргосейоге вД! 1айе1 13; тат й/: глагех; Ьеи!и 1:.= 1; /:= 2в); х:== аЯ! ъЬ)1е/ г йо Ъей!п Ы/ < г гйеп !1 аИ .Веу < а(/+1) .Йеу тйеп /:= /+1; )2 х .йеу > а[Я .кеу !Ьеп його 13; аИ:= ай 1:=/;/:= 2в! ев1; 13: а(г'):= л ев1 ! Ьей(п 1:= (л й!и 2) + 1; г:= л; тиЫ!е ! > 1 йо Ьейш 1:= !-1; з(г) епЬ; пЬИе г > 1 йо Ьей!п зс:= а(Ц! "аЯ; а(г); а(г):= х; г:= г-1; лгтг' епй ев! (йеарвогг) Программа 2.8.
Пирамидальная сортировка. вается очень эффективной, и чем больше и, тем она эффективнее — даже по сравнению с сортировкой Шелла. В худшем случае необходимы и/2 шагов, которые просеивают элементы через )оп(и/2), )оп(и/2 — !), ..., )оп(гг — !) позиций (здесь берется целая часть логарифма по основанию 2), Следовательно„на фазе сортировки происходит и — ! просенваний с самое большее !оп(гг — !), )оп(и — 2), ..., ! пересылками. Кроме того, требуются п — ! пересылок для того, чтобы отложить просеянный элемент вправо. Отсюда видно, что пирамидальная сортировка требует и !оп(и) шагов даже в худшем случае. Такие отличные характеристики для худшего случая — одно из самых выгодных качеств пирамидальной сортировки.
Не совсем ясно, в каких случаях можно ожидать наимесь. шей (или наибольшей) эффективности. Но в принципе для пирамидальной сортировки, видимо, больше всего подходят случаи, когда э,тементы более нли менее рассортированы в обратном порядке, т. е. для нее характерно неестественное д Сортировка поведение. Очевидно, что при обратном порядке фаза построения пирамиды не требует никаких пересылок. Для восьми элементов из нашего примера минимальное и максимальное количества пересылок дают следующие исходные последовательности: М м = 13 для последовательности 94 67 44 55 !2 42 18 6 М ,„ =- 24 для последовательности 18 42 12 44 6 55 67 94 Среднее число пересылок равно приблизительно †,' л ° !оп л и отклонения от этого значения сравнителшю малы.
2.2.6. Сертнреаиа с разделением После того как мы обсудили, два усовершенствованных метода сортировки, основанных на принципах включения и выбора, мы введем третий, улучшенный метод, основанный на принципе обмена. Учитывая, что сортировка методом пузырька в среднем была наименее эффективной из трех алгоритмов простой сортировки, мы должны требовать значительного улучшения. Однако неожиданно оказывается, что усовершенствование сортировки, основанной на обмене, которое мы здесь будем обсуждать, дает вообще лучший из известных до сего времени метод сортировки массивов. Он обладает столь блестящими характеристиками, что его изобретатель К.
Хоор окрестил его быстрой сортировкой 12.5, 2.6]. Быстрая сортировка основана на том факте, что для достижения наибольшей эффективности желательно производить обмены элементов на больших расстояниях. Предположим, что нам даны л элементов с ключами, расположенными в обратном порядке. Их можно рассортировать, выполнив всего а/2 обменов, если сначала поменять местами самый левый и самый правый элементы и так постепенно продвигаться с двух концов к середине.
Разумеется, это возможно, только если мы знаем, что элементы расположены строго и обратном порядке. Но все же этот пример наводит на некоторые мысли. Попробуем рассмотреть следующий алгоритм; выберем случайным образом какой-то элемент (назовем его х), просмотрим массив, двигаясь слева направо, пока ие найдем элемент а; ) х, а затем просмотрим его справа налево, пока ие найдем элемент а~ ( х. Теперь поменяем местами эти два элемента и продолжим процесс «просмотра с обменом», пока два просмотра ие встретятся где-то в середине массива.
В результате массив разделится на две части: левую — с клю- 2.2. Сортировка моссивоа чами меньшими, чем х, и правую — с ключами большими х. Теперь запишем этот алгоритм разделения в виде процедуры в программе 2.9. Заметим, что отношения ) и ( заменены иа и (, отрицания которых в операторе цикла с пред- условием — это ( и». При такой замене х действует как барьер для обоих просмотров. ртосейвте ратбтюл; тат м,х: туелП Ъе81п т:= 1; т;=- и; выбор случайного элемента х; терезе етЪ1)е а)г).йеу ( х .1сеу до т:*= т+1; нЪИе эхйеу < аЩ,йеу йа,1:= т'-1; 12 т ( т' йеп Ъея1п и:= а11); аИ:= а11); а!)):= тр1 1:=- г+1~ У '=. 7--1 евй втб! т ) 7 Программа 2.9.
Разделение, Если, например, в качестве х выбрать средний ключ, равный 42, нз массива ключей 44 55 12 42 94 06 18 67, то для того, чтобы разделить массив, потребуются два обмена 18 06 12 142~ 94 55 44 67, (2.14) н, следовательно, аа.йеу =- х.йеу й = ) + 1, ..., 1 — 1. Этот алгоритм очень прост и эффективен, так как основные величины, участвующие в сравнениях: й 1 и х, можно ва время просмотра хранить на быстрых регистрах. Но ов также может быть весьма неуклюжим, как видно из примера конечные значения индексов ~' = 5 и 1 = 3. Ключи аь ,.„а; ~ меньше пли равны ключу х= 42, ключи ате1, а, больше нлн равны х. Следовательно, мы получили два подмасснва ае йеу~(х.йеу для й=1, ..., т — 1, аа.йеУ)х йеУ длЯ й=1+1, ..., л 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
