Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 21
Текст из файла (страница 21)
После этих модификаций мы можем попытаться описать весь алгоритм в виде законченной программы (см. программу 2.(3). Анализ сортировки елттлнттелт. Поскольку на каждом проходе р удваивается и сортировка заканчивается, как только р~н, оиа требует (!оатгт! проходов.
По определению при каждом проходе все множество из и элементов копируется ровно один раз. Следовательно, обшее число пересылок равно М = и ° ((одзл1 (2.24) Число С сравнений по ключу еше меньше, чем М, так как при копировании остатка последовательности сравнения ие производятся. Но, поскольку сортировка слиянием обычно применяется прп работе с внешними запоминающими устройствами, стоимость операций пересылки часто на несколько порядков превышает стоимость сравнений. Поэтому подроб.
ный анализ числа сравнений не представляет особого практического интереса. Ллгоритат сортировки слиянием выдерживает сравнение даже с усовершенствованными методами сортировки, которые обсуждались в предыдущем. разделе. Но затраты на управление индексами довольно высоки, кроме того, существенным недостатком является использование памяти размером 2н элементов "к Поэтому сортировка слиянием редко применяется при работе с массивамн, т.
е. даннымп, расположслными в оперативной памяти. Цифры, характеризующие быстродействие сортировки слиянием в режиме реального вр ° мени, содержатся в последних строках табл. 2.9 и 2.!О. Этя показатели лучше, чем у пирамидальной сортировки, но хуиш, чем у быстрой сортировки. Ч Маиоииии, ито в итеративном варианте алгоритма бысгроя сорти. ривка трсбуетеи стек размера и, и а рекурсивном варианте ззгрггы наиигн зианитгльио больше. — Гргьи. р.д. 2. Сортировке ргеееймте жегйезогг; таг 1ЛЬт!,1! 1нс[ех; Ь,т,рд,г: 1пгезег; ир.* Ьоо[еап; [а иМеет индексы 1... 2еп) Ъезй ир:= !гие; р:= '1; терев! Ь:= 1; тп:= н; !Е ир йеа Ъеа!а 1:= 1; 1, 'и; 1с: н+1; 1; 2еп евй е!ие ЪеПш Ь:= 1; 1: н; 1;= и+1; 1;= 2еп еа4; зерее! (слияние серий из т и1 в Ь[ .[а — длина серии из т, г — длина серии изД 3Т пс ) Р йеп 4; Р е!зе 4: тт т:= т — 4; Ъ[ т > р йев г:= р е1зе г:.
т; т:=- т — г; ттЬ1!е (д~0) Л («ФО) до Ъе41а [слияние[ И а[1[ .1сгу < аИ .1сеу ФЬеп Ъе41а аЩ; а[![; Ь:. Ь+Ь; т: 1+1; 4: 4 — 1 еай е1яе Ъе4!в аЯ;= а[А, "1с:= Ь+Ь; 1:=,1 — 1; г:= г — 1 еа4 ев4; [копирование осгпатка серии из 1[ зтЪПе г к~ О 4о ЪеПю а[4[;= а[Я; 1с:= 1с+Ь;,1:=,1-11 «: «-1 еа4 1 [ копирование остатка серии из 11 ттЬ(1е а ~ О 4о Ъеа(а а[Ь) ".= аИ; Ь: Ь+Ь;1с 1+1; а т . ! — 1~ ев4 ; Ь: -Ь; г:= Ь; 1с:= 1; 1. '1 авП!т =О; ир:= -тир; р:= 2*р пв41 р еЪ и; !1- ир йеп 1ог т': = 1 !о и 4о а[11: = а[1+т![ ев4 (те«4езогг) Прегреммме 2.!3. Сортиреяяа нростмм слиянием, З.й Сортировка аовлвдоватвлькмк файлов [1б 1.3.2.
Естественнее слияние В случае простого слияния мы ничего не выигрываем, если данные уже частично рассортированы. На й-м проходе длина всех сливаемых подпоследовательностей меньше или равна 2а без учета того, что более длинные подпоследовательности уже' могут быт» упорядочены и их можно было бы сливать. Фактически можно было бы сразуслнвать какие-либо упорядоченные подпоследовательности длиной гл и п в одну последовательность из т + п элементов. Метод сортировки, при котором каждын раз сливаются две самые длинные возможные подпоследовательностн, называется естественным слиянием. Упорядоченную подпоследовательность часто называют цепочкой.
Но, поскольку слово «цепочка» чаще используется для обозначения последовательности символов, мы будем использовать слово серия, когда речь идет об упорядоченной подпоследовательности, Мы называем подпоследовательность оь ..., аь такую, что ав~(па+~ для й=), ..., ) — 1, аг,>ао (2.25) ат > а~+~, лшксимальной серией или, короче, серией. Итак, сортировка естественным слиянием сливает не последовательности фиксированной, заранее заданной длины, а (макснмальные) серии.
Серии имеют то свойство, что при слиянии двух последовательностей, каждая из которых содержит п серий, возникает одна последовательность, содержащая ровно и серий. Таким образом, на каждом проходе общее число серий уменьшается вдвое, н число необходимых пересылок элементов в худшем случае равно и (!опал], а в обычном случае даже меньше.
Ожидаемое число сравнений, однако, намного больше, так как кроме сравнений, необходимых для упорядочения элементов, требуются еще сравнения соседних элементов каждого фаяла для определения концов серии. Следующим нашим упражнением будет разработка алгоритма естественного слияния тем же поэтапным методом, который использовался при объяснении алгоритма простого слияния. Вместо массива он обрабатывает последовательный файл и представляет собой несбалансировапну|о двухфазную трехлентечную сортировку слиянием. Пусть исходная последовательность элементов задана в виде файла с, который в конце работы должен содержать результат сортировки. (Разумеется, в реальных пооцессах обработки исходные данные для сохранности сначала переписываются с ленты а рабочий файл с.) Используются две вспомогательные ленты а и Ь, Каждый проход состоит из фазы распределения, которая распределяет серии поровну из с в а и Ь, и фазы слияния, 2.
Соргмроаяа 116 которая сливает серии из а и Ь в с. Этот процесс показан на рнс. 2.13. а а а с с Ь ь я~ в фаза слиямия ~ фаза распредепеиия 1-а проход 2-и проход и-я провод Рис. 2.)3 Фазы сортировки и проходы сортировки. 17 31' 5 59' 13 41 43 67' 11 23 29 47' Э 7 71' 2 19 57' 37 61 5 17 31 59' 11 !3 23 29 4! 43 47 67' 2 3 7 19 57 71' 37 61 5 11 !3 17 23 29 31 41 43 47 59 67' 2 3 7 19 37 57 61 71 2' Э 5 7 11 13 17 19 23 29 31 37 41 43 47 57 59 61 67 71 2 — 4).
В естественном слиянии участвуют 20 чисел. Заметим, что требуются только три прохода. Сортировка заканчивается, как только число серий в с будет равно 1. (Предполагается, что в ясходном файле имеется хотя бы одна непустая серия.) Итак, пусть переменная 1 используется для подсчета числа серий, слнваемых в с. Если мы опрелелим глобальные объекты (2.26) то программу можно написать следуюшим образом: ргоседнге матата!тетке; таг Г: т!ггег; а,Ь; !аре; Ъеймз гереаг гезргйе(а); гемтйе(Ь); таге!(с)1 Йз!г!Ьи!е; теде!(а)' гете!(Ь) генгйе(с); 1: = 0;.тетке вв!11 ! = ! евй (2.271 В качестве примера в табл. 2.11 показан файл с в исходном состоянии (строка 1) и после каждого прохода (строки Таблица 2.!!.
Пример сортировки естествеииым сзияиием 2,3. Сортировка ооследоеотельиит файлов 117 Ясно, что две фазы выражаются двумя отдельными операторами. Теперь пх надо уточнить, т. е. описать более подробно. Подробные описания можно либо непосредственно вставить в текст, либо представить в вкд* процедур, и тогд» сокращенно записанные операторы следует рассматривать как вызовы процедур. На этот раз мы изберем последний способ и определим рквсейпте йЫпЪи1с, '° (иэ с в а и Ь) Ьей(п тереа1 сорупрл(с,а); Ы вЂ” сог (с) 1йеп сорутир.:,Ъ1 ппИ сог"(с) епй (2.28) ртосейв е тисгее; Ьей(п ,'иэ а и Ь в с) тереа1шсгхпии; 1::=-: 1 "1 ив61 соДЬ); К вЂ” сот"(а) Фйеп Ьей1п соруптн(а,с); (: =--.
!+1 епв (2.29) епй ртвсевпте соругии(тат х,у: саре) ," Ьей1п (перепись одной серии иэ х ву) тереа1 сору(х,у) ппм1 еос епв (2.30) Предполагается, что прн таком способе распределения в файлах а и Ь оказывается либо равное число серий, либо файл а содержит на одну серию больше, чем Ь. Поскольку соответствующие пары серий сливаются, в файле а может оказаться лишняя серия, которую следует просто переписать. Процедуры тессе и йэЫЬи1о формулируются с помощью подчиненных процедур тегдегил и сорргин, задачи которых понятны. Теперь опишем этн процедуры более подробно; онн требуют введения глобальной булевской перемет1ной сот (епб о( (пе гпп), значение которой показывает, достигнут ли конец серии.
2. Сортировка !!а ргеседпге вегяегап; Ьея!в (слияние серий из а и Ь а с) терев! 1т а',.кеу < Ь !.)геу !Лев Лера сору(а,с); 11 еог !Леп соругнп(Ь,с) еай е!эе Ьей!п сору(Ь,с)! Ы еог !Леа соругин(а,с) еай пп!!! еог ! (2.3!) Процесс сравнения и выбора по ключу при слиянии серий завершается, как только будет исчерпана одна нз двух серий. После этого остаток другой серии, который еще не исчерпан, нужно переслать в выходную серию с помощью просто~о копирования. Зто осуществляется вызовом процедуры соругин. Обе эти процедуры определены с помощью подчиненной процедуры сору, которая пересылает элемент из файла в файл у н определяет, достигнут ли конец серии.
Ее легко написать, используя операторы гесс! н ыт!Ге. Для того чтобы найти конец серии, нужно сохранять ключ последнего прочитанного (переписанного) элемента для сравнения со следующим. Зто «заглядывание вперед» достигается использованием буферной переменной файла х7. ргеспЛие сору(тат х,у: таре); тат Ьау' Иет; Ъейш геак)(х, ЬаУ); игйе~у, ЬаД; (2.32) 12ео)'(х) йеп еог:=- ггае е!зе еог:= Ьиуусеу > х!.кег епй Зги последовательности легко сливаются в одну серию, после чего сортировка заканчивается. Хотя этот пример и не при- На этом построение процедуры сортировки естественным слиянием закончено.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
