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