Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 25
Текст из файла (страница 25)
рии с 10 на Г(/], мы можем записать начальную фазу распределения следующим образом (как обычно, считаем, что на входе имеется по крайней мере одна серия): гереа1 ве!ее!гнре, соругил пп(!! ео)()0) (2.47) Но здесь мы должны остановиться и вспомнить эффект, который наблюдался прн распределении серий в рассмотренном ранее алгоритме естественного слияния: из-за того, что две серии, последовательно записанные на одну ленту, могут образовать одну серию, реальное количество серий иа лентах может не совпасть с ожидаемым. Когда алгоритм сортировки разрабатывался таким образом, что его работа не зависела от количества серий, этот побочный эффект можно было спокойно игнорировать. Но при многофазной сортировке мы особенно заботимся о том, чтобы знать точные количества серий на каждой ленте.
Следовательно, нам приходится учитывать возможность такого случайного слияния. Поэтому нельзя избежать нового усложнения алгоритма распределения. Оказывается необходимым сохранять ключ 2. Сортировка последнего элемента последней серии каждой ленты. Для этого мы вводим переменную 1аз1: аггау[1арело] о( 1лгейтег Теперь алгоритм распределения можно представить следующим образом: терся! ве1есмаре„. !х 1авг[/] ( УО] .лисеу Отеп анродолжение лретнней серии»! (2,48) соругил! 1аег[Я:= /01 .1сеу явЯ етЩ'О) Здесь содержится очевидная ошибка: мы забыли о том, что 1ав1[1] получает (определенное) значение только после переписи первой серии! Правильное решение состоит в тон, что вначале распределяется по одной серии на на>кдую из л — ! лент без обращения к 1аз1[1[. Оставшиеся серии распределяются согласно (2.49): ттЬИе еоД/О) йо Ьей!в ве1еснаре; М 1а>н[/) (/О] 3сеу йен Ьейш (лродоллсение лрехсней серии] соругил; (2.49) К ео/(/О) !Ьев с([Я т= И[/] + ! е)ае соругил еаа е!ае соругил еяй Предполагается, что присванвание значений 1ав1[л включено в процедуру соругил.
Теперь мы, наконец, готовы взяться за основной алгоритм многофазиой сортировки слиянием. Его принципиальная структура подобна основной частя программы л-путевого слияния: имеется внешний цикл, в теле которого сливаются серии, пана не будут исчерпаны все входные данные, внутренний цикл, в теле которого сливается по одной серии с каждой входной ленты, и самый внутренний цикл, в теле которого выбирается начальный ключ и элемент передается в выходной файл. Принципиальные отличия следутощие: !. На на>кдом проходе имеется только одна выходная лента вместо л/2. 2. Вместо переключения л/2 входных и л/2 выходных лент после каждого прохода ленты чередуются. Это достигается с помощью карты ленточных инденсов 1. ад Сортировка аогледовагвлвк»~к авалов !37 3.
Число входных лент меняется от серии к серии; в начале каждой серии оно определяется по счетчикам а, фиктивных серий. Если А ) 0 для всех 1, то п — ! фиктивных серий сливаются в одну фиктивную серию при помощи простого увеяичения счетчика йа выходной ленты. В противном случае со всех лент, у которых гЬ = О, сливается по одной серии, а для всех остальных лент а; уменьшается, что означает исключение одной фиктивной серии. Число входных лент, участвующих в слиянии, мы обозначаем через Ь.
4. Невозможно установить окончание фазы при помощи состояния конца файла (п — !)-й ленты, поскольку могут понадобиться дальнейшие слияния, в которых участвуют фиктивные серии с этой ленты. Вместо этого теоретически необходимое число серий определяется по коэффициентам а,. Коэффициенты а, были вычислены на фазе распределения; теперь их можно вычислить в «обратном порядке». Теперь, согласно этим правилам, сформулируем основну.о часть алгоритма многофазной сортировки, предполагая, что все и†! лент с начальными сериями перемотаиы на начало и установлены начальные значения в карте ленточных индексов 1, =1: верея! [слияние с 1[Ц...
1[п — Ц на 1[п)) %=- а[п — Ц; г)Я:= 0; тевтйе(1[![я))); гереа! 1с;= 0; (слияние одной серии) [ определение числа 1г входных лент, участвующих в слиянии ~ 1ог 1:= 1 !оп — 1 йо !1 й[Ц > О !Ьев д[1):= д[1) — 1 е!ае Ьея!в Ь:=- й+1; га[й):=- ![1) евй; !1 )с =- 0 тЬев д[п):=- а[п) + 1 е1эе «слияние одной действительной серии с 1[Ц...1[к)» г:=г — 1 вв61 г =- 0; тетсгЯАп)))' «переключение лент в карте 1; вычисление а[1) для следующего уровня»; те»туге(1' [г[п)[); 1ете1: = !еге1 — 1 ввт!! )еге1 =- О; [отсортированнЫй 6)айл находится на 1[Ц) (2.50) Операции действительного слияния почти идентична с программой л-путевой сортировки слиянием, единственнан ргайгтп ро1угог1 (ои1риг)1 (многофазная сортировка с и лентами ) совке и б; ( число лент) гуре йет = гееогй йеу: т1екег епй; горе = й(е оУ йет; гарепо 1., п; чаг 1епк, гапй (пгейег( (используются оля яюмйрования(бойла) ет: Ъоо1еап; Ъиу, йет; 1'0; 1аре; [70 -входная лента со случайньиии числами) „г: аггау [1 ..и) о11аре; ргосейаге 1йг (таг.Г", 1аре; т 1арепо); чаг й: 1пгекег; Ъей(в р:= 0; впге1п (' ТАРЕ', и; 2); ъЬИе -теор'(~) йо Ъее(п геай(Х, Ъиу); т11е(ошри1, ЪиЯеу: 5); х:= я+11 1г к = 25 ФЬеп ьей(в ггг11е1п (ои1ри1)' г:= 0 епй евй; м я Ф 0 Огепвг11е1п,(овраг); геге1(1) ~вй (йт); ргосейвге ро1урйагегог1; тт 1.
1,тХ,1П: гарепо; )с„1еге1: 1пгекег; а, а.' аггау [гарепо) оу 1пгекег; (аК-идеальное число серий на ленте.11 (ЙЦ-число Фиктивных серий на ленте Ц йп,х,т!п,г1 1пгекег; 1агг; аггау [1арепо1 ог 1пгекег; (1аз1К-ключ конечной серии на,ленте Д 1,1а: аггау [горело) ог горело; ( карты номеров лент1 ргосейвге ге1еснаре; таг 1: 1арепо; г: 1пгецег; Ьей(в Ы а[А ( ~Я+1') 1Ьев,1:= у+1 е1ао ЪейаИ а[Я = ОГЬеп Ьей(в 1ере1;= 1еге! + 1,' я:= а[111 Йю «: =- 1 !е и — 1 Ио Ъейпг 4«1;= х + а[!+13 — аИ; аИ:= х + а[!+Ц евв еай; у =1 евй; 4Я:= 4Я -1 епй; ргессйпге соругип; Ъеи!в [перепись одной серии с у0 ни леня«уД герье! гса4уО, Ьиг); пг«1е(!(Я, Ьиг); ппи! еоХ(10) Ч (Ьи'.«сеу ~ у'О! .)сЕу)1 !аз«[Я : Ь~',[сеу ев«(; Ъев!в [расг«ределение,начально«я серий) Гог Г: = 1 гь л — 1 де Ъев!в аЯ:= 1; 4«) '.= 1;,ге«гг««с(у"[«[) еий ; [еге1:= 1; /': '1; а[п[:= О," 4п[;= 01 геуеа! зе!ес««аре , 'соругип ппп! еоДуО) Ч ([=л — 1); эЪ!!е 'со~"(у') «!о Ьев!в зе!еспаре; Ъ(!аз«[Я ~ у"0( .)сеу!Ъеи Ьеи!в [продолзпение щкжней серии) соругип; !г еоу(у'О) 6ми 4Я:= 4Я + 1 е(зе сорупее ев«$ е1зе соругил епй; з«л «: = 1 !ь л — 1 «!е гезе«(Д«[); гог Е: = 1 ге л йе «[«1: = «'; гереас [слияние с «1Ц...
г(п — 1) на г(пЦ г:= «ф« — Ц! 4л):= 0; ге«гг««е(Д«[п))); геревг 7с:= 0; [слияние одной серии! Гог Г: 1 го л — 1 йе (г 4«[ > 0 !Ъеп 4«[:= 4«[ — 1 е!ге. Ъеи!в [с:= [с+1; «аЩ: = Щ евй; 1« 1с О !Ъев 4п);= 4п[ + 1 е(ее Ьей!п !слияние одного дайся«еигпе.льного опи«сена с1(Ц...Щ! ио 2 Сортировка хереа1 т:= 1; тх:= 1; т1п:= 7'[(а[Ц][ .1сеу„.
ттЯ)е т ( Ь йо Ъе81п 1;=- 1+1; х:= Дса[1]]1 Аеу; И х < т1л реп Ье81п т1л:== х; тх:== 1 епй епй; 11а[тх) содержит наименьший элемент, пересняла' его на 1[л]) ген(1'[са[тх3, Ьил; евс:=. еоЩЩтх]])1 мт(1е(1[с[я]], Ьст1 ); 11 (Ьи('.1сеу > у[са[тх]]7.1сеу) Ч еа1 2Ьеп Ье8!п (сброс этой ленты) та[тх]: — сс[1с]; й:=- 1с — 1 епй аиЯ Й = 0 епй; х:= х — 1 пп01 х = 0; гетет(1Уп]]); 1ит(1 [с[п]], т[п]); [переклточение ленты] тп:= т[п]; с(п:= д[п]; х;= а[п — Ц; Гог 1: = л йоттп1о 2 оо Ье8!п тИ:= 1[1 — Ц; с([1]:= а[1 — Ц; а[1]:=- а[с'-Ц вЂ” и епй; 1[Ц: тп; а[Ц:= атп„а[Ц:= х; (отсортированный сйайл находится на 1[Ц] 11вт(Яс[1]], т[Ц); )ете1:= 1ете1 — 1 ппЯ 1ете1 = 0; епо [ро(урйатезвгт]; Ье8Ра [формирование случаиного Файла) 1еп» с= 200; гапс1:= 7789; теряет тапа: = (13 1071*гапс1) отой 21474836471 ЬиУ.(сеУ:= галс(41т21474841 ттг11е(7'О, Ьир'); 7еи8'; а ЙЩ - 1 апЯ 1еп8 = 0; гегес(у'О)1 1121(у'О, 1); ра 1урйагезог1 епй Программе 2.16.
Ммотофевяая еортярояяа, 2.8 Сортаровва последовательпь~х файлов разница заключается в том, что алгоРитм исключения ленты несколько проще. Как производится поворот карты ленточных индексов и соответствующих счетчиков с1 (и перевычисление коэффициентов а; при переходе на низший уровень)— очевидно, это можно подробно видеть в программе 2.16, которая полностью описывает алгоритм многофазной сортировки. 2.3.$. Распределение начальных сернй Мы пришли к сложным программам последовательной сортировки, поскольку более простые методы, работающие С массивами, требуют наличия достаточно большой памяти с произвольным доступом, чтобы хранить все сортируемое множество данных. Очень часто такой памяти нет, вмесго нее приходится использовать достаточно вместительные запоминающие устройства с последовательным доступом. Мы видим, что методы последовательной сортиронки, рассмотренные выше, не требуют практически никакой оперативной памяти, кроме буферов для файлов п, разумеется, самой программы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
