Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 23
Текст из файла (страница 23)
Г [пуг) в у [пй + Ц... у [п) ) «установка входных лент»; Е:=0; у г= ай+1; [уьггндекс выходной летпы) гереаг Е:= Е+1; «слияние серии а с входных лент на Е [Д» 11 у С и Яеп у г= у+1 е!зе у г= пБ+1 ппб>1 «все входные ленты исчернаньп>; «переключение ленты» ип111 Е = 1; [отсортированный Файл находится да лен>не у [Ц) еаа Прежде всего уточним операцию копирования, которая используется при начальном распределении серий; вновь введем вспомогательную переменную для буферизации последнего считанного элемента Ьи[: ггет и заменим «перепись одного отрезка с ЕО на ленту Е» оператором гереаг геагЕ(у О, Ьиу"); гогугеЯЯ„ЬиЕ" ) (2.38) пп111 (ЬиЕ Есеу ) „> 0[.усеу) >Е ео[(Е'О) Перепись серии заканчивается, либо когда встречается первый элемент следующей серии (Ьиу.Угеу) ЕОЕ.Угеу), либо когда достигается конец всего входного файла (еоЯО)).
2.3. Сортировка вовлвйовательвьм файлов !2в Теперь в алгоритме сортировки остались операторы 1) установка входных лент; 2) слияние серии с входных лент на ленту 1Ц; 3) переключение ленты и предикат 4) все входные ленты исчерпаны, которые нужно определить более подробно. Во-первых, мы должны аккуратно вести учет текущих входных файлов. Заметим, что количество «активных» входных файлов может быть меньше чем У/2.
Действительно, максимальное число входных файлов может быть равно числу серий; сортировка заканчивается в том случае, когда остается только один файл. Причем может оказаться, что количество серий в начале последнего прохода сортировке меньше чем лй. Поэтому мы вводим переменную тт1 для обозначения числа текущих входных файлов. Инициацию И мы включим в оператор (1) следукнцим образом: 1Е 1 < лй гйеп И:= 1 е)яе И:=- пй; Гвг 1:= 1 1в И во гевег(/'[т[Щ Понятно, что оператор (2) должен уменьшать значение й1, как только исчерпывается какой-либо входной файл. Следовательно, предикат (4) легко можно, выразить отношением И=О Оператор (2) уточнить труднее; он содержит циклический выбор наименьшего ключа из текущих входных данных; выбранный таким образом элемент, посылается в выходной файл, т. е.
на текущую выходную ленту. Этот процесс осложняется еще тем, что нужно искать конец каждой серии. Конец серии считается достигнутым, если (1) очередной ключ меиыпс текущего, или (2) достигнут конец входного файла. В последнем случае лента исключается из работы путем уменьшения И, в первом случае отрезок закрывается, т. е, файл перестает участвовать в дальнейшем выборе элементов, но только до тех пор, пока не окончится формирование текущей выходной серии.
Отсюда ясно, что необходима вторая переменная А2 для обозначения числа входных лент, которые в текущий момент используются для выбора следующего элемента. Это значение вначале полагается равным ят и уменьшаегся, когда какая-либо серия закрывается по условию (1). К сожалению, недостаточно ввести переменную й2: мало знать число лент — нужно знать точно, какие именно ленты ( используются длл Формирования файла) (конеи лентпы) ргойгаог Ыапсейтетйе (оитриг); '1сбалансщюванная п-путевая сортировка слиением) еоавх и ° б» пЬ = 3; (число лент) зуре Йет гееогй кеу: )атейст еой; Горе = й»е охнет; тарепо =- 1..
и; чаг 1епй, тапа: 1птееет; сот: Ьоо1еап; ЬиУ'. йет; у"О; таре; ()'Π— входная Лента со случайными числами» у', аггау (1.. и) о1нре; ргоеейвге йвт(тагУ: заре'; п: тарепо); гаг г; »птекет; Ьер»а ичч!е(п('ТАРЕ', и:2); х ."= О; зтЫ»е -~евку') йо Ьефа теай(т", ЬиЯ; иттте(оитрий Ьиуйеу: 5); х:= с+1; Кх = 25 ГЫеа Ьейт ттЮе1п(оитрит); г; = 01' епй епй 11 е,Ф 0 реп тйе)п (оитрит); тететЯ епй (1йн); ргоеейвге тарететеесотЦ айаг »,т,тхйх: торепо; И,Ь2 11 тптейет; х, тт; арекет; О та; аггау 1тарепо) ар гарево; Ьейт ! распределение начальных серий на ЦЦ... Цпй) ) 1ог т: = 1 го пЬ йо тетттйе(»р))' ,т';= пЬ; 1:= О; гереаг Ы у' < т1Ь гЬеп т' ', = т+1 е1ве ): = 1; (перепись одной серии с т 0 на лаптуна 1:= 1+1; гереа1 теай(»'О, Ьиу)'„тт йе(у" Я, Ьиу') иарй (Ь4 Яеу > у'0),йеу) '/ еоу(»'О) штгй сои'(у'0); р 1:= 1 Го и йо щ 1= Ц гереа$ (слияние с 4)Ц...
т(пЬ) на 1)пЬ + Ц... Цп) ] 1г 1 < пЬ гЬеп И;= 1 еЬе И:= пЬ, (И-число входных лент на этои фазе) гогй: 11оИйо ьааьа газет(йр)»); !ЬгИ)тИ); ФЪ, за)1):= тр) епй; 1:=- 0; [1-число сливаемых серий) ,!': =- пб+1; [[-индекс выходной ленты ) герое! [с!!сочное серий с ![1)... ![к1) на ![А) 7с2! = 81; 1: 1-)-1; [!с2-число входных лент, участвуюших в слиянии) сереем [выбор наименьшего элемента) 1:=- 11 тх:=* 1,' гп!и:= 1[!а[1))[.!сеу', ягЬИе !' < 7с2 до Ье81п с':.=- с+1; х '.= Я!а[!))).)сеу; 11 х < тт Йеп Ьей!и'т!и: — - х; тх: =- ! епд епд 1 [наименьший элемент на !а[тх), пересылка его на ![!) ) геаАЯма[тх)), биД; еог;= еоЩ[га[тх))); иг!геД[с[Д, ЬиД; И го! 1Ьеп Ьейт гессе(Я!а[тх)[); [исключение ленты ) га!тх):= — са[7с2); !а[7с2) с= !а[!с[); 7с1:= 7с1 — 1,' )с2:= !с2 — 1 епд е)ае И Ьсд'.7сеу > Яа[тх))) .)сеу 1Ьеп Ье81п сх:= са[тх]: са[тх) ".= га[!с2)' га[7с2) 1= !х; !с2: 7с2 — 1 епд па!И й2 = О; Ку < и сЬеп,7:=,[+1 е)ае !: пй+1 падИ )с1 = О; Гое с: = 1 !о пб до Ьей[п гх:= с[!); с[!): а[!+пб); с[7+гсб):= рх еад ппИ1 ! = 1; гага![7 [с[1))); 7!г![! [с[1)), г[1))1 [отсортированный файл нахойшпсн на ![1) ) вад [гаретег8еэог!); Ъей)п [формирование случайного файла !'0) !епа 1= 200; тапА:= 7789; гесс!!се[ГО); гереаФ гапд:= [181071агапА) спад 2147483847; Ьи7'.lсеу:= юапА д[Я 2147484; сгпге(!О, Ьи!); !епд;=и 7епк — 1 опйй !епя = 0; гезег[!0); !!э![!'О, 1)," !арен! егкегог! епд, Программа 2ЛЬ, Сортировка сбалаисироваиимм слиянием.
г. Саят,р --, >28 еще участвуют в игре. Очевидный прием — использовать массив булевских переменных, отражающих активность лент. Однако мы предпочитаем другой метод, при котором более эффективно работает процедура выбора, являющаяся в конечном счете наиболее часто повторяющейся частью алгоритма.
Вместо булевского массива вводится вторая карта лент 1а. Эта карта используется вместо 1 так, что га]1] 1а ]й2] — индексы лент, участвующих в работе. Итак, оператор (2) можно записать следующим образом; й2:= й1; терев««выбор минимального ключа, пусть 1а)тх) — номер его ленты»; ген(Я>а]тх)), Ьи7"); (2.39) т> е(УКД), Ь~4); Ы еоЯЯа)тх))) йеа «исключение ленты» е)зе. К Ь>р".кеу >,1'))а(тхЩ.йеу йеп «закрыть серию>> вао1 й2 = О Поскольку количество устройств-носителей магнитных лент, доступных в вычислительной системе, обычно довольно мало, алгоритм выбора, который нужно уточнить иа следующем этапе, может также представлять собой простой линейный поиск. Оператор «исключение ленты> предполагает уменьшение й1 и й2, а также изменение значений индексов в карте >а. Оператор «закрыть серию> просто уменьшает А2 и должным образом переупорядочивает компоненты 1а.
Подробно это показано в программе 2.15, которая является окончатель- . ным уточнением (2.37) при помощи (2.39). Заметим, что ленты освобождаются процедурой геп>г(ге, как только прочитана последняя серия, Оператор «переключение ленты» разработан в соответствии с данными ранее пояснениями. 2.2.4. Миогофазная сортировка Теперь мы знаем необходимые приемы и подготовлены к тому, чтобы разработать и запрограммировать другой алгоритм сортировки, работающий более эффективно, чем алгоритмы сбалансированной сортировки, Мы видели, что при сбалансированном слиянии устраняются операции простого копирования, поскольку распределение и слияние объединены в одну фазу.
Возникает вопрос: можно ли еще лучше использовать имеющиеся ленты? Да, это действительно нозможно; очередное усовершенствование заключается в том, чтобы отказаться от строгого понятия прохода, т. е. использовать ленты более хитрым способом, чем тот, когда считают, что всегда имеется Ф/2 входных лент и столько же выход- 2.3. Сортировка лоследователвкмл файлов 129 ных, и меняют ролями входные и выходные лепты после каждого отдельного прохода. При этом понятие прохода становится нечетким. Этот метод был изобретен Р..Л.
Гилстадом [2.3) и назван лгногофазиой сортировкой. Вначале проиллюстрпруем его на примере работы с тремя лентами. В каждый момент элементы сливаются с двух лент на третью. Как только одна из входных лент окажется исчерпанной, она сразу становится выходной лентой для слияния с той ленты, которая сше ие исчерпана, и с той, которая до этого была выходной. М !2 !3 Тяи 11 12 13 14 16 16 16 16 14 12 8 8 7 6 4 0 6 4 3 2 0 4 4 1 0 2 2 2 1 0 1 1 1 1 1 0 0 1 и 0 О 0 Рис. 2.14. Миогофазиая сортировка слияиием с тремя лентами, содерясащими 21 серию. Рис.
2.16 Миогофазиая сортировка слияиием с шестью леитамя, содерлсащими 66 серий. Поскольку мы знаем„что и серий на, каждой входной ленте преврашаются в и серий па выходной ленте, иам нужно только вести список числа серий на каждой ленте (вместо того, чтобы определять действительные клкзчи). На рис. 2.14 предполагается, что вначале две входные леиты !! и 12 содержат соответственно 13 и 8 серий. Таким образом, на первом «проходе» 8 серий сливаются с !! и !2 на !3, па втором «проходез оставшиеся 5 серий слипаются с !3 и 11 на 12 и т.
д, В копне работы на ленте !! содержится отсортированный файл. Второй пример демонстрирует многофазный метод с 6 лентами. Пусть вначале имеются 16 серий на 11, 15 — иа !2, 14 — иа 13, 12 — на !4 н 8 — иа 15; на первом частичном 2. Сортировки !30 1 2 3 5 8 13 21 1 1 2 3 5 8 13 Таблица 2.!4. Идеальное распределение серий на пити лентах 1 а о а1в а'и ам а'" х' ап> 1 в ак о 1 2 3 4 5 О 1 2 4 8 15 1 1 2 4 8 16 о 1 2 4 7 14 о 1 2 3 6 12 1 5 9 17 33 65 Из табл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
