Лекции по информатике (984119), страница 21
Текст из файла (страница 21)
В худшем случае нужно и(2 перемеще- ний элементов на логарифмические расстояния 1оиа и,/2, 1ой2[11(2 — 1), .... Следователь- но, фаза сортировки потребует и. — 1 вставку в пирамиду с самое большее 1оу [и — 1), 1оа '111 — 2), ..., 1 перемещениями. Кроме того, нужно еще и, — 1 перемещение для вставки в пирамиду после извлечения ее верхушки. Каждая вставка занимает пе более 1ой и, ша- гов, что дает Общую оценку и 1оя и,. Для боэльших и это даже лучше сортировки Шелла с ее и . 11аилу иная производительность пирамидальной сортировки достигается при обрат1ьд ной упорядоченности исходных элсмслпов. При этом фаза порождения пирамиды всюбще и 1о8и не требует перемещений. Среднее лисло перемещений равно причем отклонения 2 От этОГО зна ления нс'велики.
В 1981 году п1эоф. Э. Б. Дс'йкстра предложил гладкий вариант пирамидальной сорти- 347 ровки, дающий линейное время для почти отсортированного массива. Однако эта сорти- ровка не получила широкого распространения из-за чересчур сложного алгоритма. 6.2.2.6 Быстрая сортировка Займемся теперь улучшением обменной сортировки наихудшей из прост>ых. Забегая вперед, скажем, что она будет кардинально улу плена, и оправдает полученное в свое время от ее автора Чарльза Энтони Ри >арда Хоара многообещаннцес название бысгпрая соргпироокп. Мы знаем, что быстрыми являн>тся те сортировки, .в которых осуществляются перестановки на, болыпие расс~о~~~~.
Отвлечемся от ооычного для фон Неймановской ~а~~~~ исполнения вслепую, нс глядя на данные, и отсортируем п элементов, .уже упорядоченных в обратном порядке. Меняя местами первый с последниь> всего за 3 операции, тогда как черепашьим пузырьковым одношаговым движением это >ке расстояние будет пройдено за бп. — 9 » 3 операций! Далее процесс повторяется для 2 и и, — 1 и т. п.
пар, равноотстоя- 1 щих от середины элементов. Этот пример. ,вероятность которого очень мала и равна —, и! сор>пируе>пся за линейное время. Видимо, подобная идея дальних сиъ»метричных обменов навела автора па следующий алгоритм сортиро»ки: выберем наугад какой-нибудь промежуточный [розделя>ощий) элемент х (зерно'1 и будем просматривать сортируеъгый массив слева, пока не оонар1 жим элемент и,, > х, затем, проходя этот же ма~сии справа.
,будем искать элемент а < х. Чтобы ликвидировать обнаруженную инвсрсин>, поменяем местами эти два элемента [они в сил1 поиска с концов к середине находятся на довольно больпюм расстоянии) и продолжим процесс просмотра и перестановки, пока оба прохода не встретятся где-то в середине массива. Этот процесс классифицирует сортируеълые элементы относительно зерна сор>пировки х: в нужной ли половине массива они находятся. [Здесь уже можно начать подозревать, что ненужные половины будут впоследствие отброшены как это уже имело место в деревьях поиска или при дихотомии в упорядоченных таблицах.) В результате массив окажется разбитым на левун> часть, с ключами, меньшими [или равными) х, и правую, с ключами большими [или равными) х.
Этот процесс представим в виде процедуры, причем отношения < и > заменяются на < и >, а в заголовке цикла Мп1е используется их отрицания > и < соответственно. ргосес1пге раг1,>11оп; ъаг», х: Ые>п; Ьеп1п 1; и; 1' Взять промежньпочиъ>й злеъ>еип> х (зерно) ) гереаС ънЬ11е а[1[ < х до — 1; ънЬ11е х < аЦ г1о 1:.1 11'[> < - Я СЬеп Ьеп1п >ч:- а[!~; а[1~: - а[1 ~; а[~ ~: — »; 1: 1 3 3 — 1;. епс1; ппЫ1 >1; епс1; При этом зерновой элемент х выступает в качестве барьера для обоих просмотров.
Если в последовательности 44 55 12 42 94 06 18 67 взять зерновой элемент х = 42, то при ее разделении на подпоследовательности произойдут два обмена: 18 ~ †» 44 и 06 с †55, последний из которых меняет третий элемент с пятым. Ключи аг, ..., а,, г не больше ключа х = 42. Ключи а,.г, ..., а„не меньше х. Следовательно, массив разделен на две части: И: 1 < сс < г; ая < х, И: 1 < Й < н: х < ас-. Этот алгоритм прост и эс1гфективсн в памяти прямого доступа, однако, в случае идентичных ключей разделение все равно потребует гг,г2 обменов. Этих необязательных обменов можно избс:жз,ть, если добавить 1гавенсгво в условия просмат1эиваюгцих циклов. тлЫ1е(а~1~ < = х) с1о г -~- 1: Мг11е(х <-- аИ) с1о ): — 1 — 1; При этом мы вынуждены будем отказаться от барьерно-элементного способа организации циклов ради маловероятного случая.
Чтобы раздс лениг" упорядочивало, надо продолжить его автономное применение к ка,ждой из получившихся частей, пока разбиение не приведет к одноэлементым частям. Естественной реализацией этого алгоритма, является рекурсивная процедура с~игс1:хогг() ргосес1пге ьсшс1с8огь(ъсаг а: зес1): 1' БъсстРаЯ соРтиРовка ХоаРа сг 1' Основной принцип: производим разделение лсассива в граниоах /Ь,.Рг/ так, чтобы .левая по.лавина содержала элементы, меньшие некоторого х, ггравая— больисие сг ргосес1пге ВесЯог$(Ь, К: гпс1ех); лиг г, с: шс1ех: х, гч: 11еш; Ьеи1п х:-- а[(Ь + В.) с11ь 2~: 1' выбираем зерно — средний элелсент ~ 1:-- Ь; 1с; 1' Разделение массива / гер еаза 1' Два, совмесйенньсх пРосмотРа во вспгРечньсх напРавленилх (с С С, г — — ССС) сс исЫ1е а~1) < х с1о 1; тиЫ1е а(~( > х г1о 3: .1 11 1 < 1 ФЬеп Ьеиш 1' Обмен элеменгпов, находяи1ихая не в своих, половинах г иг; а(1 ( (1: Б(; а(д ( ит 1; .(: .( епс1; ппИ 1:- 1; 11' Е < ~ ФЬеп КесБогГ1Е, ~); 1' Сортировка левой полстены перепоручается вновь активируемому экзелтляру эпгой же процедуры лг 1Г 1 <.
Е ФЬеп ВесЯогг(1, В); 1 Сортировка правой половины перепоручается вновь активируемому экземпляру этой эсе процедуры ~ епс1; 1' Весэ'огг г Ьеиш фон~ ВесБог$(1, г1); епс1; В наше многопропсссорное и многоядерное время нельзя не заметить, что сортировка Хоара, поддастся распараллеливанию на, (1ой'и( процессорах. (Поэтому Ссджвик в своей книге (88( называет быструю сортировку алгоритмом «разделяй и властвуй». ( Мы не будем избегать рекурсии по техническим причинам, как это делалось 30 и более лет назад, и напишем еще и нерекургивную версию как альтернативный вариант быстрой сортировки. Суть итеративного решения заключается во введении списка отложенных заданий на дальнейшее разделение. Поскольку на каждом этапе возникает две задачи по разделению, одну из них можно выполнить сразу, а другую — отложить, поместив в упомянутый список. При этом существенно, что отложенные запросы выполняются в обратном порядке: второй полумассив главного массива будет отсортирован последним.
Обратный порядок вызван тем, что сортировку второй половины необходимо выполнять одновременно с первой, в соответствии с моделируемой нами логикой рекурсивной программы ЯигскЯоггО. Со стеком и обратным порядком выполнения подзаданий обхода мы уже встречались при нерекурсивном обходе дерева. И здесь этот порядок предопределен семантикой рекурсивного выполнения быстрой сортировки, характерным элементом которой является рекурсивное разветвление в два места. Задача упрощается еще и тем, что в стек заносятся не сами сортируемые гюдпоследовательности, а их границы в общем массиве. Заметим, что экспериментальное сравнение рекурсивной и нерекурсивной версий обнаруживает их одинаковую временную сложность, и сегодня единственной причиной уклонения от рекурсии может быть только использование языка программирования,не обеспечивающего рекурсивного вызова процедур ~старые версии Фортраг|а и Бейсика и ассемблер, па, котором всс придется моделировать вручную, даже имея аппаратную поддержку стека).
350 ргосес1 иге С1и1с]сЯот1Х11 [айаг а: яес1); ( Быстпрая сортпировка Хоара — нерекурсивная,1 ( Основногл приниин: список яранглгг требуемых раздетгениг1 инверти1гуется в стпеке Суре Т гесогс1 ( Эжмеггт стека — ераничиая, пара 3 1., К: 1пс1ех егн1; ргосес1пге Сгеаге[чаг я: ЯСас1.); ГппсСюп ЕгггрСу[~аг я: йас1с]: Ьоо1еап; КппсС1оп %хе[чаг я: ЯСас1с): шСедег; 6шсС1оп 1'ггя1г[чаг я: йас1с; С: Т): Ьоо1еап; 6шсСюп Рор[гтаг я: ЯСас1с): Ьоо1еап; СппсСюп Тор[ътаг я: ЯСас1с): Т; ргосес1ш е Ьгеяггоу[чаг я: Ыас1с]; лтаг яС: ЯСас1с; ( о( Т тг г, ], Ь, В.: 1пс1ех; х, гх: Ыеш; С: Т; Ьедш СгеаСе[яС); С.Ь:= 1; 1.В:- и; Рггя1г[яС, С); гереаС (Выбор запроса из стпека3 1.:=- Тор[яС).Ь; В: Тсэр[яг).11; Рор[яС]; гереаС (разделение А(Ц,.Л(Ц зг х; — а[[1.
г К] сСЬ' 2]; ( выбираем, зерттовог1 эяеллеттт 3 Ь; ]: — К; гереаС (рттзделеттгге,массива[ Мн1е а[1] < х с1о с- г + 1; гл Ы1е а[]] > х с1о 11" 1 - --- ] СЬеп Ьефп ж:-- а[г ]: а[г]:= аЦ]: а[]]: - гъ", : — г+1; :=- .) епс1; н7>$11 ! 11 > =О К 1Ьен 1>ед!и ( о>иклатЭь>вась> заа>рос па сортировку правой половииь> в стек а !а Весло> 1(7', В) >7 1.Ь:- 1.К: — К !'па!>(в1, 1); епс1; ( Вторую полгюипу сортируем >иъмесЭлсипо КесБог1(й, Я;,7 К; >; ( Ь и В теперь оера7>ичива>оп> левую часть 7> пп01 1 ъ — — К; ппИ! Еп>р1у(а$); епг1; Проанализируем алгоритм быстрой сортировки.
Сначала оценим трудоемкость процесса разделения. Выбрав некоторое зерновое значение х мы проходим по всему массиву. и выполняем ровно и сравнений. Число обменов можно определить из следующих вероятипастиых соображений: при зафиксированном зс рновом элементе х ожидаемое число обменов равно числу элеък нтов в левой части разделяемой последовательности, т. е. п — 1, у.множенному на вероятность того, что при обмене каждый такой элемент попадает в нужную половину на свое место.
Для левой части обмен происходит, если элеълент перед этим и — (х — 1) находился в»раной части. Вероятность этого равна . Получить ожидаемое и число обменов можно, усреднив эти ожидаемые значения для всевозможных границ х: 1 - и — (х — 1) 1 — п(и — 1) 2па — 3и+ 1 и, — 1>п, ЛХ вЂ” — (х — 1) — — и(п, — и)— и п и2 ~ 2п бп 6 к=> в=а Наилучшим образом быстрая сортировка работает тогда, когда всякий раз в качестве зернового элемента выоирается медиана -- среднезначный элемент >ъиножества, делящий его на два равпомощных подмножества (с точностью до 1 элемента). В этом случае каждый процесс разделения расщепляет массив на две половины и для сортировки требуется всего 1г>и и проходов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
