AOP_Tom3 (1021738), страница 82
Текст из файла (страница 82)
(ср. с фазами 1-5). Преимущества схеиы Бенчера можно видеть, если ииеется, например, только пять начальных серий: осциллирующая сортировка (ее модификация из упр. 2) выполняла бы четырехпутевое слияние (на фазе 2), за которым следовало бы двухпутевое слияние с общей стоимостью 4 + 4+ 1+ 5 = 14, тогда как схеиа Бенчера выполняла бы двухпутевое слияние (на фазе 3), за которым следовало бы четырехпутевое слияние с общей стоимостью 4+ 1+ 2+ 5 = 12.
Оба метода также требуют небольших дополнительных затрат, а именно — однократной перемотки перед окончательным слиянием. Точное описание метода Бенчера содержится ниже, в алгоритме В. К сожалению, соответствующую процедуру, по-видимому, трудней понять, чем запрограммировать; легче объяснить данный метод компьютеру, чем программисту! Частично зто происходит по той причине, что рекурсивный метод выражен в итеративном виде и затем подвергнут некоторой оптимизации; читатель, возможно, обнаружит, что приходится несколько раз проследить за работой алгоритма, прежде чем станет понятно, что же происходит. Алгоритм В (Осииллируюи»аи сортировка с "»1ерекрестним" распределением). Этот алгоритм берет первоначальные серии и распределяет их по лентам, время от времени прерывая процесс распределения, чтобы слить содержимое некоторых Фаза 1 Фаза 2 Фаза 3 Фаза 4 Фаза 5 Фаза 6 Фаза 7 Фаза 8 Фаза 9 Распределение Распределение Слияние Распределение Слияние Распределение Слияние Распределение Слияние А» А,А» А» А»А1 А» А»А» А» А» 4 3 4 3 4 3 4 3 4 лент (рис.
77). В алгоритме используется Р-путевое слияние и'предполагается, что имеется Т = Р + 1 > 3 накопителей на магнитной ленте (НМЛ) (хе считая устройства, которое может применяться для хранения исходных данных). НМЛ должны допускать чтение как в прямом, так и в обратном направлениях; они обозначены числами О, 1,..., Р. Используются следующие массивы. Р [у], 0 < у < Р: Число фиктивных серий, наличие которых предполагается в кон- це у'-й ленты А[1,]], 0 < 1 < Ь, Здесь Ь вЂ” достаточно большое число, такое, что будет введено О < у < Р: Рь Ы начальных серий.
Если А[1,1] = А > О, то на ленте у имеется серия номинальной длины Рь, соответствующая "уровню Г работы алгоритма. Эта серия — восходящая, если ь. четно, и нисходящая, если А нечетно. А[1,]] < 0 означает, что на уровне 1 лента у не используется Инструкция "Записать начальную серию на ленту у" является сокращенным обозначением следующих действий. Установить А[1,1] +- О. Если исходные данные исчерпаны, то увеличить О[у] на 1, в'противном случае записать серию на ленту ] (в порядке возрастания).
Инструкция "Произнести слияние на ленте у е используется как краткое обозначение следующих действий. Если 0 [1] > 0 для всех 1 ф ], то уменьшить О [1] на 1 при всех 1 ~ у и увеличить О[у] на 1. В противном случае произвести слияние одной серии нв ленте у со всех лент 1 ф у, таких, что 0 [1] = О, и уменьшить 0 [1] на 1 для всех остальных [Ф я'. Рис. 77. Осциллнрующая сортировка с "перекрестным" распределением. В1. [Начальная установка.) Установить 0[у] < — 0 при 0 < ] < Р. Установить А[0, 0] +- — 1, 1 е- О, д е- О. Затем записать начальную серию на ленту у' для 1 < у < Р. В2. (Ввод завершен?] (В этот момент лента й пуста и всякая другая лента содержит максимум одну серию.) Если еще есть исходные данные, перейти к шагу ВЗ. Однако если ввод исчерпан, то перемотать все ленты у ф д, такие, что А[О,Я четно; затем выполнить слияние на ленту д, читая все только что перемотанные ленты в прямом направлении, а остальные ленты — в обратном.
Этим завершается сортировка; результат находится иа ленте д в порядке возрастания. ВЗ. [Начать новый уровень.] Установить!»-1+ 1, 㻠— д, в +- 0 и с!» — [4+ 1) пюс1 Т. Записать начальные серии на ленты [с7+1) шос) Т, где 1 < 1 < Т вЂ” 2. [Таким образом, начальные серии будут записаны на все ленты, кроме лент 4 и г.) Установить А[1,д) +- — 1 и А[1,гз» вЂ” — 2. В4.
[Можно ли выполнять слияние7] Если АП-1, д) ф в, вернуться к шагу ВЗ. В5. [Слияние.] [В этот момент А[! — 1,9) = А[1,уЗ = в при всех 1' ф д, у' ~ г.) Выполнить слияние на ленте г, читая в обратном направлессии. [См. выше определение этой операции.) Затем установить ⻠— в+ 1, !»- ! — 1, А[1, г!» — в и А[1,9)»- — 1. Установить 㻠— (2д — г) пюс1Т.
[В общем случае имеем г = [д — 1) шас1 Т, если в четно, и г = [д + 1) пюс! Т, если в нечетно.) Вб. [Завершена ли формирование уровня?] Если ! = О, перейти к шагу В2. В противном случае, если А[1,1] = в для всех у' ф с7 и ! ~ г, перейти к шагу В4. В противном случае вернуться к ВЗ. в Чтобы показать работоспособность этого алгоритма, можно использовать доказательства наподобие рекурсивной индукции так же, как для алгоритма 2.3.1 Т. Предположим, что мы начинаем с шага ВЗ при 1 = !о, д = до, в» = АИо, (с7о+1) спас! Ту и в = А[!о, [до — 1) спас) Т3. Допустим, кроме того, что либо ве = О, либо в = 1, либо в+ — — 2, либо в = 3, либо ..
Можно проверить по индукции, что алгоритм, в конце концов, придет к шагу В5, не изменив строки А с 0-й по 1о-ю. При этом будут получены следующие значения переменных: ! = !о+ 1, д = оо ~ 1, г = оо и в = в+ илн в . Причем выбирается знак "+", если вэ —— 0 или [вэ — — 2 и в ф 1), или (в+ —— 4 и в ф1,3),илн .,изнак "—" — если(в =1ив+ фО) или[в =Зив».ф0,2), или .
- .. Приведенный здесь "набросок" доказательства не очень элегантен, но ведь и сам алгоритм сформулирован в виде, который больше годится для реализации, чем для проверки правильности. На рнс. 78 показана эффективность алгоритма В, выраженная средним числом слияний каждой записи в зависимости от 5 — числа начальных серий, причем предполагается, что начальные серии приблизительно равны по длине. (Соответствующие графики для многофазной и каскадной сортировок приведены на рис. 70 и 74.) При подготовке рнс.
78 учтено небольшое усовершенствование, упомянутое в упр. 3. Метод, некоторым образом связанный с рассмотренным и названный круговой сортпироокой (йугабпй вогС), разработан Р. М. Карпом (В. М. Катр) и основан на теории слияния в прямом порядке, приведенной в разделе 5.4.4. [См.
СашЫпаСопа! А18аг!йшв, ес!!сесе Ьу ВапбаИ Вцв11п (А!8ог!1Ьш!св Ргевв, 1972), 21-29.] Прямое чтение. Схема осциллирующей сортировки, по-видимому, требует возможности чтения в обратном порядке, поскольку приходится где-то накапливать длинные серии. Тем не менее в работе М.
А. Соесхс Ргос. АГХР5 Ярг!пл,7а1пС Сошр. СолЕ 25 [1964), 599-607, найден способ выполнения осциллирующей сортировки с помощью только прямого чтения и простой перемотки. Предложенный метод в корне отличается от остальных схем, которые мы рассматривали в этой главе, по следующим причинам. !з т-з й 9 у 0 7 о й о о 5 4 о" з т-4 Т40 Т=7 т=о т= 1о о 1 2 5 10 20 50 100 200 500 1000 2000 5000 Начальные серне, Х Рис. ТВ. Эффективность осцнллнрующей сортировки, использующей метод алгоритма В н упр. 3.
а) Данные иногда записываются в начвло ленты, причем предполагается, что данные, которые находятся на середине ленты, не разрушаются. Ь) Бее начальные строки имеют фиксированную максимальную длину. Условие !а) нарушает свойство "первым включается — первым исключается', которое, как мы предположили, является характеристикой чтения в прямом порядке. Однако оно может быть надежно реализовано, если между сериями оставлять участок чистой ленты достаточной протяженности и если в нужные моменты пренебречь ошибками четности. Условие (Ь) оказывается до некоторой степени противоречащим эффективному использованию выбора с замещением.
Осциллирующая сортировка Гоетца !Сое!н) с прямым чтением имеет одно сомнительное достоинство — зто один из первых алгоритмов, который был запатентован как алгоритм, а не как физическое устройство ~ Г 5. Ра1еп! 3380029 !1968)); если зто не удастся оспорить, то нз факта патентования следует, что алгоритм нельзя использовать в программе без разрешения владельца патента. Метод Бенчера !осциллирующая сортировка с обратным чтением) был запатентован 1ВМ несколькими годами позже. (Увы, мы являемся свидетелями конца эры, когда удовольствие от открытия нового алгоритма само по себе считалось достаточным вознаграждением! К счастью, осциллирующвя сортировка не настолько уж хороша, чтобы из-за нее стоило ломать копья.
Будем все-таки надеяться, что здравомыслящие ученые, придумывая новые алгоритмы, будут продолжать делать свои идеи достоянием всех. Что касается тех недальновидных людей, которые хранят новые алгоритмы в строгом секрете, то нужно сказать, что они немного выигрывают по сравнению с п»ирокой доступностью своих результатов, поскольку право собственности сохраняется в течение лишь ограниченного времени.) Центральная идея в методе Гоетца состоит в таком использовании лент, чтобы каждая лента начиналась с серии относительной длины 1, за которой следовала бы серия относительной длины Р, затем — Рз и т. д.
Например, если Т = 5,. то сортировка начинается следующим образом ["." указывает текущее положение головки чтения/записи на каждой ленте). Операция Т1 Т2 Распределение ..4» .А» ТЗ Т4 ТЗ .А» А» Л» Фаза 1 .А» Аь .Л» .4» Фаза 3 Распределение .Л» .А» А» А» А» А» А» А» А»»6».А» '4гА» Фаза 5 Распределение .А» Слияние '$». фаза 6 А» А» А» .А! А» .А» А» Фаза 2 Распределение .А» И так далее. Во время фазы 1 лента Т1 перематывается и одновременно на Т2 записываются исходные данные; затем перематывается Т2 и одновременно на ТЗ записываются исходные данные и т. д.
В конце концов, ко»да исходные данные исчерпаны, начинают появляться фиктивные серии, н иногда необходимо вообразить, что они записаны явно на ленте полной длины. Например, если Я = 18, то серии А» на Т4 и Т5 будут зафиксированы во время фазы 9; нам придется продвинуться вперед по Т4 и Т5 при слиянии с Т2 и ТЗ на Т1 во время фазы 10, так как надо добраться до серий А» на Т4 и Т5 для подготовки к фазе 11. С другой стороны, фиктивная серия А» на Т1 необязательно должна существовать явно. Таким образом, "конец игры" несколько замысловат. Еще с одним примером применения этого метода мы встретимся в следующем разделе Фаза 2 Слияние !4г $г !4, $» А» А» Фаза 4 Слияние .'6».
15». 41». А, А,. 41гА» фаза 8 Слияние»5», А» А». $»А» $, » '[» Фвзв 9 Распределение А»..А» А» .А» А» .А» А» .А» А» Фаза 10 Слияние А»А». $гА» 34гА» $» Л» 15» -4» Фаза 11 Слияние А»А»А»в $» $» 15»»5» $» М»»5» з»» 'Стоимость" Примечание 5 [Т5 не перематывается] 4 [Перемотка всех лент] 4 [Т4 не перематывается! 4 [Перемотка всех лент] 4 [ТЗ не перематывает ся] 4 [Перемотка всех лент] 4 [Т2 не перематывается] 4 [Перемотка всех лент) 4 [Т1 не перематывается] 4 [Нет перемотки] 16 [Перемотка всех лент] 51ПРДжНВНИЯ 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
