Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 44
Текст из файла (страница 44)
142. [Подготовка к иросмотру.) Если е = О, установить» +- 1, у» — Ф, й»- Х + 1, 1»- 2Ю: если е = 1, установ ть 4 +- Х+ 1, у +- 2Х, й +- 1, 1+- Х. (Переменные », у, Й, 1 указывают текущие позиции во "входных массивах", из которых выполняется чтение, и в "выходных массивах", в которые осуществляется запись,) Установить И»- 1, у' +- 1. (Переменная Н задает текущее направление вывода; у устанавливается равной О, если необходимы дальнейшие просмотры.) ХЗ. [Сравнение К;: Ку.) Если К; > К„перейти к шагу Х8. Если 1 = у, установить В» +- В, и перейти к шагу Х13.
1ч4. [Пересылка Вь) (Шаги Х4-Х7 аналогичны шагам МЗ-М4 алгоритма М.) Установить В» +- Вп Й»- Й + И. »45. [Ступенька вниз7[ Увеличить 1 на 1. Далее, если К; ~ < Кп вернуться к шагу ХЗ. гчб. [Пересылка В..) Установить В» +- В, к+- й+ и. Х7.
[Ступенька вниз7) Уменьшить у на 1. Далее, если Кчл < К, вернуться к шагу Хб; иначе — перейти к шагу Х12. Х8. [Пересылка В .) (Шаги Х8-Х11 двойственны шагам Х4-Х7.) Установить В»»- В., й» вЂ” 5+И. »чй. [Ступенька вниз7[ Уменьшить у на 1. Далее, если К ил < К., вернуться к шагу ХЗ. »ч10. [Пересылка В».) Установить В»»- В;, 1» +- я + И.
Х11, [Ступенька внизу[ Увеличить 1 на 1. Далее, если К; » < Кь вернуться к шагу Х10. »412. [Переключение направления.) Установить у»- О, д +- -И и выполнить замену Й +» 1. Вернуться к шагу ХЗ. »"(13. [Переключение областей.) Если у = О, установить з» вЂ” 1 — з и вернуться к шагу Х2. В противном случае сортировка будет завершена. Если з = О, установить (В~ „..., Вм) +- (Вл+ы..., Вел). (Если результат можко оставить в области (Вне ы..., Вял), примерно в половине случаев последнее копирование оказывается необязательяым.) 1 В ятом алгоритме есть одна небольшая тонкость, которая объясняется в упр. 5.
Запрограммировать алгоритм Х для машины НХХ нетрудно, ио можно проанализировать ход его выполнения и без разработки программы. Если массив случаен, то в нем имеется около 1Х восходящих серий, так как К, > Кьы с вероятностью 1 3 5. Подробная информация о количестве серий при несколько отличных предположениях была получена в разделе 5,1.3. При каждом просмотре (на каждом проходе алгоритма) чиню серий сокращается вдвое (за исключением необычных случаев, таких, как ситуация, описанная в уцр. 6).
Следовательно, число просмотров составляет, как правило, около 18~1Х = 18Ф вЂ” 1. При каждом просмотре необходимо переписать все Ф записей, и, как показано в упр. 2, ббльшэл часть времени затра чивается на выполнение шагов ХЗ-Х5, Х8, Х9. Если считать, что равные ключи встречаются с малой вероятностью, то время, затрачиваемое во внутреннем цикле, можно охарактеризовать следующим образом. Рне.
ЗО. Сортировка метелом слияния. Операции СЕРА, Уй, 1Е ЕтА, 1ЕС 1ИС, 1ЮА, СИРА, ВСЕ йтХ, 1ЕС РЕС, 1РХ, СНРХ, ЗСЕ Шаг Время 3.5и Зи би Зи бп л ь(„"' Либо Значит, прн каждом просмотре иа каяслую запись затрачивается 12.5 машинных циклов и общее время выполнения асимптотически приближается к 12.5Ф1ЕХ как в среднем, так н в наихудшем случаях. Это происходит медленнее быстрой сортировки н не настолько лучше времени работы пирамидальной сортировки, чтобы оправдать вдвое болыпий расход памяти, так как асимптотическое время выполнения программы 5.2.3Н равно 18йг 1ЕК. В алгорятме М граяьцы между сериями полностью определяются стуценькамн вниз.
Такой подход обладает тем потенциальным преимуществом, что исходные массивы с преобладанием возрастающего или убывающего расположения элементов могут обрабатываться очень быстро, но прн этом замедляется основной цикл вычислений. Вместо того чтобы проверять ступеньки вниз, длину серий можно установить принудительно: считать, что все серии исходного массива имеют длину 1, после первого просмотра все серии (кроме, возможно, последней) имеют длину 2,..., после А-го просмотра все серии (кроме, возможно, последней) имеют длину 2". В отличие от "естественного" слияния в алгоритме К такой способ называется простым двухцутевым слиянием. Алгоритм простого двухпутевого слияния очень напоминает алгоритм Х вЂ” он, по существу, описывается той же блок-схемой.
Тем не менее методы отличаются один от другого, и поэтому стоит записать весь алгоритм целиком. Алгоритм 8 (Сортировка методом простого дорхиутеоого слияния). Как и в алгоритме Х„при сортировке записей Вм..., Ви используются две области памяти. 81. ]Начальная установка.) Установить е ~- О, р +- 1. (Смысл переменных з, 1, у, й, 1 и и приводится в описании алгоритмами. Здесь р — размер восходящих серий, которые будут сливаться во время текущего просмотра. Другие переменные й и г предназначены для отслеживания количества неслитых элементов в сериях в ходе выполнения алгоритма.) 82. [Подготовка к просмотру.] Если е = О, установиты е — 1, у +- Х, й е- Ж, 1+- 2Ж+ 1; если в = 1, установить 1+- йг+ 1, у +- 2йг, к с- О, 1+- Х+ 1.
Далее установить д +- 1, й ~- р, г +- р. 83. (Сравнение К,: К .] Если К, > К, перейти к шагу 83. 84. (Пересылка Во] Установить и +- й + д, Вь +- В». 85. (Конец серии?) Установить 1 <- 1+ 1, о <- о — 1. Если й > О, вернуться к шагу БЗ. 86. ]Пересылка В;.] Установить к с- к + д, Далее, если й = 1, перейти к шагу 813; в противном случае установить Вь Ф- Ву. БТ.(Конец серии?) Установить 1 <-,у — 1, г е- г — 1. Если г > О, вернуться к шагу Бб; в противном случае перейти к шагу 812. 83.]Пересылка В~.] Установить Й +- й + д, В» <- Ву. 89.
]Конец серии?) Установнть у <- 1 — 1, г <- г — 1. Если г > О, вернуться к шатт 83. 810. (Пересылка Вь] Установить к +- й + И. Далее, если к = 1, перейти к шагу 813; в противном случае установить Вь +- Вь 811. (Конец сернну] Установить 1 +- 1+ 1, й <- й — 1. Если й > О, вернуться к шагу 810.. 812. (Переключение направления.] Установить й +- р, г <- р, И +- — И и выполнить замену Й +э 1. Если ( — 1 с р, вернуться к шагу 810; в противном случае вернуться к шагу БЗ. 813.
(Переключение областей.) Установить р < — р + р. Если р ( Х, установить э +- 1 — х и вернуться к шагу 82. В противном спучае сортировка будет завершена. Если е = О, установить (Вы " Вн) <- (Вн+м",Вел). (Последнее копирование необходимо выполнять тогда и только тогда, когда (13Х] нечетно, независимо от распределения записей в исходном массиве. Таким образом, можно заранее предсказать положение рассортированного массива н копирование, скорее всего, станет излишним.) $ Пример выполнения алгоритма представлен в табл.
2. Довольно удивительно, что этот метод прекрасно работает и тогда, когда Х не является степенью 2. Не все Таблица 2 СОРТИРОВКА МЕТОДОМ ПРОСТОГО ДИУХПУТЕВОГО СЛИЯНИЯ ! 426 ( 154 ~ 509 ) 612 ~ 275 ~ 170 154 ( 612 653 426 275 ! 677 897 653 509 426 612 боЗ 677 703 ~ 170 ) 897 ! 275 ~ 653 908 ~ 426 897 1 653 170 509 908 1 897 677 703 765 1 908 426 503 509 о12 503 ~ 087 503 703 087 503 061 087 061 087 ~ 512 ! 061 ! 908 ( 512 677 ~ 509 703 765 ! 154 503 512 612 154 170 275 677 ~ 765 ~ 703 061 ) 765 087 612 512 061 275 170 154 765 897 908 Алгоритм 1 (Сорглнроека посредством слияния списков). Предполагается, что в звпнсяхВО..., Вк содержатся ключи Кы..., Км и поля связи Ьм..., Х,~, в которых могут храниться числа от — (Ф+ 1) до (Ф+ 1). В начале н в конце массива имеются искусственные записи Ьо и Ьл+~ с полями связи Во н Вл+м Этот алгоритм сортировки списков устанавливает поли связи таким образом, что записи оказываются связаннымн в порядке возрастания.
После завершения сортировки Ьо указывает на запись с наименьшим ключом; при 1 < к < Ю связь 1» указывает на зались, следующую за В», или Ь» = О, если В» — запись с наибольшим ключом (см. формулы 5.2.1-(13)). слнваемые серии имеют длину 2», тем не менее никаких явных мер предосторожности на случай таких исключений предусматривать не приходится! (См.
упр. 8,) Проверки ступенек вниз в прежнем алгоритме заменены посредством уменьшения переменных о и г и проверки равенства нулю. Благодаря этому время выполнения на машине И1Х асимптотически приближается к 11йг1ВХ машинным циклам, что несколько лучше результата, которого удалось достичь в алгоритме Х. На практике имеет смысл комбинировать алгоритм б с методом простых вставок. Вместо первых четырех просмотров алгоритма 8 можно методом простых вставок рассортировать группы, скажем, из 16 элементов, исключив таким образом довольно расточительные вспомогательные операции, связанные со слиянием коротких массивов. Как и в случае быстрой сортировки, такое комбинирование методов не влияет на асимптотическое время работы, но дает, тем не менее, немалую выгоду. Рассмотрим теперь алгоритмы Х и Б с точки зрения выбора структур данных.
Почему необходима память для 2Ю, а не для Ю записей? Причина относительно проста: мы работаем с четырьмя списками переменного размера (два входных списка и два выходных списка в каждом просмотре); при этом для каждой пары последовательно распределенньпс списков используется стандартное понятие "совместный рост", обсуждавшееся в разделе 2.2.2. Но в любой момент времени половина памяти не используется, и после некоторого размышления становится ясно, что в действительности для наших четырех списков следовало бы воспользоваться соленым распределением памяти.
Если к каждой из йб записей добавить поле связи, то все необходимое можно проделать, пользуясь алгоритмами слияния, которые выполняют простые манипуляции связями н совсем не перемещают сами записи. Добавление Ю полей связи, как правило, выгоднее добавления пространства памяти еще для Ф записей; отказавшись от перемещения записей, можно сэкономить и время. Итак, рассмотрим следующий алгоритм.
В процессе работы этого алгоритма записи Ве н Вм+1 выполняют роли головных элементов двух линейных списков, подсписки которых в данный момент сливаются, Отрицательная связь означает конец подсписка, о котором известно, что он упорядочен; нулевая связь означает конец всего списка. Предполагается, что В > 2.
Через "[Ь„[ е р' обозначена операция "Присвоить Х, значение р или -р, сохранив прежний знак Х,". Такая операция легко реализуется на компьютере 81Х, но, к сожалению, не на большинстве других моделей компьютеров. Нетрудно изменить алгоритм, чтобы получить столь же эффективный метод для большинства других машин. 11. [Подготовить два списка.] Установить Ье < — 1, Ь~д+~ +- 2, Ь, ~- — (1+ 2) при 1 < 1 < Ф вЂ” 2 и Ьм ~ +- Ьм +- О. [Созданы два списка, содержащих записи Вы Вз, Вы ° ., и Вэ, В1, Ве,... соответственно; отрицательные связи указывают, что каждый упорядоченный подсписок состоит всего лишь из одного элемента. Другой способ выполнения этого шага, если принять во внимание упорядоченность, которая могла присутствовать в исходных данных, рассмотрен в упр.
12.) Ь2. [Начать новый просмотр.] Установить в +- О, г <- Л + 1, р +- Х„п +- Ьь Если д = О., выполнение алгоритма завершается. [В процессе каждого просмотра р и д "пробегают" по спискам, которые подвергаются слиянию; э обычно указывает на последнюю обработанную запись текущего подсписка, а 1 — на конец только что выведенного подсписка.) 13. [Сравнение Кр. Кю] Если Кр > Кю перейти к шагу Ьб. Ь4. [Продвинуть р.] Установить [Ь>[ +- р, э +- р, р +- Ьр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
