Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 78
Текст из файла (страница 78)
Сб. ]Продвижение.] Уменьшить пг на 1. Если гп > О, вернуться к шагу Сб. В противном случае уменьшить А на 1; если А > О. установить гл с- А [Т вЂ” у' — 13 — А[Т вЂ” Я и вернуться к шагу Сб, если пт > О. В противном случае уменьшить у на 1; если у' > О, перейти к шагу С4, в противном случае увеличить 1 на 1; если 1 < Т вЂ” 1, вернуться к шагу СЗ.
В противном случае перейти к шагу С2, СТ. [Подготовка к слиянию.] (К этому моменту начальное распределение завершено и таблицы АА, 0 и ТАРЕ описывают состояние всех лент в данный момент.) Установить И[А] е — АА[Й+ Ц при 1 < Й < Т и установить Р1ЕЗТ +- 1. (Переменная Р1ЕЗТ принимает ненулевое значение только во время первого прохода слияния.) С8. [Каскад.] Если 1 = О, остановитьсн; сортировка завершена, вывод находится на ТАРЕ[13.
В противном случае при р = Т вЂ” 1, Т вЂ” 2, ..., 1 (именно в таком порядке) выполнять р-путевое слияние с лент ТАРЕ [13, ..., ТАРЕ [р] на ТАРЕ [р+ Ц следующим образом. Если р = 1, моделировать однопутевое слияние посредством обычной перемотки ТАРЕ [23 и замены ТАРЕ[13 е+ ТАРЕ[23. В противном случае, если Р1ЕЗТ = 1 н 0[р — 13 = М[р — 13, моделировать р-путевое слияние, просто поменяв ТАРЕ [р3 е+ ТАРЕ [р+ Ц, перемотав ТАРЕ [р3 н выполнив вычитание И[р — Ц из каждого 0[Ц,...,0[р-13, И[13, ...,М[р-Ц.
В противном случае вычесть И[р — Ц из всех И[Ц,...,М[р — Ц. Затем слить по одной серии с каждой ТАРЗИ, такой, что 1 < 3 < ри 0[33 < И[13; вычесть единицу из каждого 0[у], такого, что 1 < у < р и 0[33 > И[Я, и помесить выводную серию на ТАРЕ[р+ Ц. Продолжать работу, пока ТАРЕ [р3 не станет пустой. Затем перемотать ТАРЕ [р] и ТАРЕ [р+ Ц. С9. [Опуститься на уровень.] Уменьшить 1 на 1, установить РХЕЗТ +- О и установить (ТАРЕ[13,..., ТАРЕ[Т]) +- (ТАРЕ[Т],,ТАРЕШЦ. (К этому моменту все 0 и М вЂ” нули; таковыми они и останутся.) Вернуться к шагу С8.
$ На шагах С1-Сб алгоритма С выполняется распределение, на шагах С7-С9— слияние. Эти две части совершенно независимы одна от другой, н можно было бы хранить И[А] и АА [й+ 13 в одних и тех же ячейках памяти. Анализ каскадного слияния. Каскадное слияние поддается анализу с ббльшим трудом, чем многофазное. Но этот анализ особенно интересен, поскольку содержит много замечательных формул. Настоятельно рекомендуем читателям, интересующимся дискретной математикой, самостоятельно проанализировать каскадное распределение прежде, чем чишашь дальше. Ведь числа имеют так много необычных свойств, открывать которые для себя -- одно удовольствие! М[ы обсудим здесь лишь один из многих подходов, обращая особое внимание на методы получения результатов, Для удобства рассмотрим ~тучай для шести лент.
При этом будем стараться получить формулы, которые обобщаются для любого Т. Соотношения (1) позволяют получить первую основную систему: )ае — ( )Е г+( )а г — ( )а в+ °" для О < га < Т-2. К счастью, эту сумму можно вычислить стандартными методами (это фактически пример 2 из раздела 1.2.6), Теперь можно вычислить коэффициенты при В(г) — 91(г)А(г) и т.
д, Рассмотрим, например, коэффициент при гг"' в 11(г) — дв(г)А(г), Он равен (3+~и+3) +в .~~- (3+гп+й)(23) (-1) +" й>0 ь>е как следует из результата примера 3, приведевпюго в разделе 1.2.6. Таким образом, получены формулы А(г) = 4В(г)А(г), В(г) = 91(г) 4(г) — ее(г), С(г) = В(г)А(г) — В(г), Х~( ) = ев( )А(г) — В( ) Е( ) = 94( ).4( ) — ев(г). Кроме того, имеем е„+в = а „следовательно, гА(г) = Е(г) и .4(г) = ев( И94( ) — г).
(9) Производящие функции были выражены прн помощи д-многочленов, поэтому желательно лучше изучить 9. В этом отношении полезно упр. 1.2.9-16, так как оно дает выражение в замкнутом виде: д„(г)— ((44 — гг+ 1г)/2) ~ + ((~~4 — гз — 1г)~2)~ ~~ г,4 — -~ . (16) Все упрощается, если теперь положить г = 2 вшд: ~ (2'1" д) 2 д д (совд+(ьбпд)в +'+(совд-вв(пд)з'"+' сов(2т+Цд 2 сов д сов д (Такое совпадение приводит к мысли, что многочлены 9„,(г) хорошо изучены в математике. Действительно, заглянув в соответствующие таблицы, мы видим, что д„,(г), по существу, является многочленом Чебышева второго рода, а именно— ( — 1)'"б'з (г/2) в обычных обозначениях.) Теперь можно определить корни знаменателя в (9): уравнение ог(2 в1пд) = 2 вшд сводится к сов9д = 2вшдсовд = вш2д. Решения этого соотношения получаем, если только хдд = 2д + (2п — -')х; все такие д дают корни знаменателя в (9) при условии, что совд ф О. (Если совд = О, то д (ю2) = (2ш+ 1) никогда не равно ~2.) Следовательно, получаем восемь различных корней: 94(г) — г = О при 2 в(п =»к, 2 вш ~ЯЯ, 2 гйп в4 в", 2 вш гг Я, 2 в1п гг~ Я, 2 гйп ( Я, 2 ил Ьвг к, 2 юп ггв.
Так как д» (х) — многочлен степени 8, значит„учтены все корни. Первые тря нз этих зпаченнй дают 9в(г) = О, так что дв(в) и 94(г) — г имеют в качестве общего делителя многочлен третьей степени. Остальные пять корней управляют аснмптотнческим поведением коэффициентов А(в), если разложить (9) на элементарные дроби. Переходн к рассмотрению общего случая для Т лент, положим В» = (4Й + 1) в/ /(4Т вЂ” 2). Производящая функция .4(в) для Т лент каскадных чисел принимает вид 4 .о гв (12) 2Т вЂ” 1, ~-' 1 — г/(2в1пв») -т~г<»<~'т/г) (см. упр.
8); следовательно, а„= — чэ савв В» ~ —. 2Т вЂ” 1 (,2в1пв») — твг<«<(тгг) (13) Соотношения (8) приводят теперь к аналогичным формулам: 4 / Ь„= — ~ В» .3В.~ —, и 2Т-1 '1,2.1 В,) ' -т1г<»<(т~г) 4 / 1 с„= — г совВ»совбв» ~, ) 2Т вЂ” 1 '» 2в1пв») -тгг<»<(т(г) (14) / 1 И„= — ~~~ савв» сов 79» ~ —. 2Т вЂ” 1 ~2в1пв») -тр<»< ~тхг1 я т. д.
В упр, 9 показано, чта этн уравнения справедливы для всех п > О, а не только для больших п. В каждой сумме член с Ь = О значительно превосходят все остальные членьн особенно если и достаточно велико. Следовательно, "отношение роста" есть — ж -Т вЂ” — + — + 0(Т ).
1 2 1 (15) 2в1пво я в 48Т Каскадная сортировка впервые была ис«ледована У. К. Картерам (см. Ж. С, Сахвег, Ргос. 1ИР Сапйтевв (1962), 62-66), который получил численные результаты для небольшнх значений Т, н Дзвидом Э. Фергюсоном (см. Е.
Регйпвоп, С.4СМ 7 (1964), 2971, который открыл первые два члена в асимптотяческом поведении (15) отношения роста. Летом 1964 года Р. У. Флойд (К. %. Иоу«() получил явный вид 1/(2в)пвв) для отношения роста, так что точные формулы моглн быть использованы для всех Т. Глубокий анализ каскадных чисел был независимо выполнен Дж. Н. Рэйнн (см. 6. Х. Влпеу, Сапа«11ал Х Ма»Ь.
18 (1966), 332-349), который столкнулся с ннмн совершенно другим путем, не имея дела с сортировкой. Райки заметил принцип "отношения диагоналей", представленный на рнс. 73, н вывел много других интересных свойств этих чисел. Флойд н Рэйни в сваях доказательствах оперировали матрнцамн (упр. 6). Модификация каскадной сортировки. Если добавить еще одну ленту, то почти все операции перемотки в процессе каскадной сортировки можно совместить.
Например, можно выполнить слияние Т1-Т5 на Т7, Т1-Т4 на Тб, Т1-ТЗ на Т5 (которая к этому моменту уже перемотана), Т1-Т2 на Т4 н начать следующий проход, когда на Т4 будет перемотало сравнительно немного данных. Эффективность этого процесса можно предсказать на основании изложенного выше анализа каскадного метода (подробности приводятся в разделе 5.4.6). Схема "компромиссного слияния", которая включает многофазную и каскадную схемы как частные случаи, была предложена Д.
Э. Кнутом в САСМ 6 (1963), 585-587. Каждан фаза состоит из (Т вЂ” 1)-, (Т вЂ” 2)-, ..., Р-путевого слияний, где Р— любое фиксированное число между 1 и Т вЂ” 1. Если Р = Т вЂ” 1, значит, это многофазный метод; если Р = 1, зто чистый каскадный метод; если Р = 2, это каскадный метод без фаз копирования. Анализ такой схемы бьш проделан в работах С. Е. Нас)ке, 1ВМ 5узгешз Х 5 (1966), 226-247„и %'.
Н. Вигбе, Ргос, 1Р(Р Сопйгеза (1971), 1, 454-459. Бурж нашел производящую функцию 2', Т„(з)аа для каждого (Р, Т)-компромиссного слияния, обобщающую соотношение 5.4.2 — (16). Он показал, что наилучшее значение Р (с точки зрения наименьшего числа обрабатываемых начальных серий) как функции от з' при о' ~ оо (если непосредственно использовать схему распределения и пренебречь временем перемотки) есть соответственно (2,3,3,4,4,4,3,3,4) при Т = (3,4,5.,6„7,8,9,10,11).
Эти значения Р с ростом Т сильнее отклоняются в сторону каскадного, а не многофазного метода, н оказывается, что компромиссное слияние никогда не станет существенно лучше каскадного. С другой стороны, при оптимальном выборе уровней и распределении фиктивных серий, как описано в разделе 5.4.2, чистый многофазный метод кажется наилучшим среди всех компромиссных методов слияния. К сожалению, оптимальное распределение сравнительно трудно реализовать. В работе ТЬ.
Е. Ло)шзеп, ВХТ 6 (1966), 129-143, исследовано сочетание сбалансированного и многофвзиого слияний; модификация сбалансированного слияния с совмещением перемоток предложена в работе М. А. Гоетца (М. А. Соесз), Щйа) Сошрпсег (ЪегЪ Напс)Ьоо)с, М. К1егег, С. А. Когп (Хеш Уогк: МсСгав-НШ, 1967), 1.311-1.312, Можно представить себе и многие другие гибридные схемы. УПРАЖНЕНИЯ 1. [10] Используя табл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
