Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 20
Текст из файла (страница 20)
сОРТНРОВнА пОследОВАтельных ФАйлОВ 2,3.4. Простое слияние К сожалению, алгоритмы сортировки, рассмотренные в предыдущей главе, неприменимы, если сортируемые данные ие помеша!отса в оперативной памяти, а, например, расположены на внешнем запоминающем устройстве с последовательным доступом, таком, как магнитная лента. В этом случае мы описываем данные как (последовательный) файл, который характеризуется тем, что в каждый момент имеется непосредственный доступ к одному и только одному элементу. Это — строгое ограничение по сравнению с возможностями, которые дает массив, и поэтому здесь приходится применять другие методы сортировки.
Основной метод в это сортировка гоэ дз Сортировка последовательно~к файлов слнлниьсн. Слияние означает объединение двух (или более) упорядоченных послеловательностей в одну упорядоченную последовательность прн помощи циклического выбора элементов, доступных в данный момент.
Слияние — намного более простая операция, чем сортировка; она используется в качестве вспомогательной в более сложном процессе последовательной сортировки. Один из методов сортировки ьлиянием называется простым сгиянием и состоит в следующем; 1. Последовательч эсть а разбивается на две половины Ь и с. Последователю.ости Ь и с слвваются при помощи объединения отдельных элементов в упорядоченные пары.
3. Полученной последовательное ги присваивается имя а, повторяются шаги 1 и 2; на этот раз упорядоченные зары сливаются в упорядоченные четверки. 4 Г1редььд)шие шагй повторя;отса: четверки сливаются в восьмер;л и весь процесс продолжается до тех пор, пока ие будет упорядочена вся последовательность, ведь длины сливаемых последовательностей каждый раз удваиваются. В качестве примера рассмотрим последовательность 44 55 12 42 94 18 06 67 На первом шаге разбиение дает последовательности 44 55 !2 42 94 18 06 67 Слияние отдельных компонент (которые являются упорядоченными последовательностями длины 1) в упорядоченные пари лает 44 94 ' 18 55 ' 06 12 ' 42 67 11овое разбиениЕ пополам и слияние упорядоченных нар лают 06 12 44 94 ' 18 42 55 67 Третье разбиение и слияние приводят, наконец, к нужному результату: 06 12 18 42 44 55 67 94 Операция, которая однократно обрабатывает все множество данных, называется фазой, а наименьший подпроцесс, который, повторяясь, образует процесс сортировки, пазывается проходом или этапом.
В приведенном выше примере сортировка производится за три прохода, каждый проход состоит из фазы разбиения и фазы слияния. Для выполнения сортировки требуются три магнитные ленты, поэтому процесс называется трехленточньтм слиянием. ыо 3. Сортировка Собственно говоря, фазы разбиения не относятся к сортировке, поскольку они никак не переставляют элементы; в ка- . ком-то смысле они непродуктивны, хотя н составляют половину всех операций переписи. Их можно удалить, объединив фазы разбиения и слияния.
Вместо того чтобы сливать элементы в одну последовательность, результат слияния сразу распределяют на две ленты, которые на следующем проходе будут входными. В отличие от двухфазного слияния этот ме. тод называется однофазным или сбалансированным слиянием. Оно имеет явные преимущества, так как требует вдвое меньше операций переписи, но это достигается ценой использования четвертой ленты. вьмодиой массив входной массив Рис. 2Л2. Сортировка двух массивов методов простого саиипви. Разберем программу слияния подробно; предположим сначала, что данные расположены в виде массива, который, однако, можно просматривать только строго последовательно.
Другая версия сортировки слиянием будет основана на файловой структуре, это позволит сравнить эти программы и показать строгую зависимость формы программы от представления ее данных. Вместо двух файлов можно легко использовать один массив, если рассматривать его как последовательность с двумя концами. Вместо того чтобы сливать элементы из двух исходных файлов, мы можем брать их с двух концов массива. Такнат образом, обгций внд объединенной фазы слияния-разбиения можно изобразить, как показано на рис, 2.!2. Направление пересылки сливаемых элементов меняется (переключается) после каждой упорядоченной пары на первом проходе, после каждой упорядоченной четверки на втором проходе и т.
д,; таким образом равномерно заполняются две выходные последовательности, представленные двумя концами одного массива (выходного). После каждого прохода два массива меняются ролями: входной становится выходным и наоборот. Программу можно еще больше упростить, объединив два концептуально различных массива в один массив двойной 2.8, Сортировал последовательных Файлов Пусть индексы ! н ! указывают два исходных эл» ента, тогда как и и ! обозначают два места пересылки (сч. рнс. 2.12). Исходные данные — зто, разумеется, элементы а>, ..., а, Очевидно, что нужна булевская переменная ир для указания направления пересылки данных; ир = ггие будет означать, что на текущем проходе компоненты а>...,, а.
будут пересылаться «вверх» — в переменные а +ь ..., ае„о тогда как ир = !а!зе будет указывать, что а,+ь ..., а»„должны переписываться «вниз» вЂ” в а>, ..., а,. Значение ир строго чередуется между двумя последовательными проходами. И наконец, вводится переменная р для обозначения длины сливаемых подпоследовательностей (р-наборов). Ее начальное значение равно 1, н оно удваивается перед каждым очередным проходом. Для простоты мы будем считать, что и — всегда степень двойки. Итак, первая версия программы простого слияния имеет такой внд: ргосейнге гпегяевогг; тат 1,(,й,1: !п>(ех; ир: Воо!еап! р: (п!ейег! Ьей1в ир:= ггие; р;= 1; гереа! ( инициация индексов) !1 ир !Ьеп Ьея(в 1: 1; 1;= и; !с:= и+1; 1:= 2*и епй е1эе Ьея1в (с:= 1; ! и а и; 1:= и+1; ! ',= 2«и епй; «слияниер-лаборов последовательностей ! ит' в последовательности А и !»; ир:= — ир; р:= 2»р нп!Пр =и епй (2,2! ) На следуклцем этапе мы уточняем действие, описанное на естественном языке (внутри кавычек).
Ясно, что этот проход, обрабатывающий и элементов, состоит нз последовательных слияний р-наборов. После каждого отдельного слияния направление пересылки переключается из нижнего в верхний конец выходного массива или наоборот, чтобы обеспечить одинаковое распределение в обоих направлениях. Если сливаемые элементы посылаются в нижний конец массива, то индексом пересылки служит й н А увеличивается иа 1 после длины. Итак, данные будут представлены следующим образом: а, 'аггау(! ..2 «и] о! !ге>и (2.20) 112 2. Сортировка каждой пересылки элемента.
Если же они пересылаются в верхний конец массива, то индексом пересылки является ! и ! после каждой пересылки уменьшается на 1, Чтобы упростить операцию слияния, мы будем считать, что место пересылки всегда обозначается через Ь, и будем менять местамп значения Ь и ! после слияния каждого р-набора, а приращение индекса обозначим через Ь, где И равно либо 1, либо — 1. Уточнив таким образом «конструкцию», мы получаем л: ==. 1; т:= и; 1т-номера слиеаемых элемента«1 терев! <1: р; г: р; т: гл — 2«р; «слияиие <! элементов из ! и г элементов из у, индекс засылки есть Ь с приращением Ь»; (2 221 Ь: -Ь; обмен значениями * и ! ввгй и< = О На следующем этапе уточнения нужно сформулировать саму операцию слияния. Здесь следует учесть, что остаток подпоследовательности, которая остается непустой после слия- ния, добавляется к выходной последовательности прп помощи простого копирования, ттЫе О?ФО) Л (гФО) до Ьея1и 1 'выбор элементи из 1 или Я К а1!! .!геу < аЦ .Ьеу 1Ьеи Ьей1п «пересылка элемента из ! в Ь, увеличение ! и Ь» ! г!:= а — 1 еай е1зе Ьей1п «пересылка элемента из ! в А; увеличение! и Ь»; г: —: г — -1 епй епй; «копирование остатка последовательности !»1 «копирование остатка последовательности у» После уточнения операций копирования остатков программа будет ясна во всех деталях.
Перед тем как записать ее полностью, мы хотим устранить ограничение, в соответствии с которым л должно быть степенью двойки. На какую часть алгоритма это повлияет? Легко убедиться в том, что в более обшей сптуации лучше всего использовать прежний метод до тех пор, пока это возможно.
В данном случае это означает, что мы продолжаем слияние р-наборов, пока длина остатков входных последовательностей не станет меньше р, Это влияет только на ту часть, где определяются значения У.д. Сортировка иоеледоеательныл Файлов ыз д и г — длины последовательностей, которые предстоит слить. Вместо трех операторов г):= р; Г;=,0; ат:= гп — 2 в (т используются следующие четыре оператора, и, как может убедиться читатель, здесь эффективно применяется описанная выше стратегия; заметим, что и обозначает обшее число элементов в двух входных последовательностях, которые осталось слить: Н и- р 4)аеп г):=р е!ве гу:=и; и:=и — т); И и) р 4)теп г:=р е(зе г;=и; и:=и — г", И наконец, чтобы обеспечить окончание работы программы, иржно заменить условие р= п, управляющее внешним циклом, на р~ и.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
