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