Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 89
Текст из файла (страница 89)
Последующие уровни, очевидно, сохраняют 2~ '- упорядочение> поскольку они обладают»вертикальной» периодичностью порядка 2~ (Можно представить себе -ео на линиях -1, -2, ... н +со — на линиях 2', 2'+ 1, ....) гуишсроглура. Сеть (а) впервые была рассмотрена в работе М. Почб, Ч. Рег!, 1. Кпбо1рЬ, М.
Вайо, .УАСМ 36 (1989), 738-757; сеть (Ь) — в работе Е. В.. Сапбе16, Я. С. '1Ч111шзпзоя, Ипевг апд Мп1116пеаг А18ейга 29 (1991), 43-Ы, Интересно отметить, что в случае (а) имеем 27»а = Сп где Сг определено в упр. 32 [Дауд и др., теорема 17„', таким образом, изображения Р самого по себе недостаточно для того, чтобы охарактеризовать поведение периодической сети. 64. Следующее построение выполнено в работе Л)га1, Кош)оз, Бзещег461 [РОС5 33 (1992), 686-692).
Оно показывает, как рассортировать т~ элементов с четырьмя уровнями то элементных сортировщиков: предположим, что сортируемые элементы суть нули и единицы; пронумеруем линии (а Ь с) = от~ + Ьгп + с при 0 < а Ь е < т. Первый уронена сортирует линии ((а, Ь, (Ь+ й) гпое1 гл) ) 0 < а, Ь < т) при 0 < й < гп; пусть аь — число единиц в й-й группе из тг линий. Второй уровень сортирует ((а„Ь, й) ) О < о,Ь < гл) при О < й < т; число единиц и й-й группе тогда будет таким: и отсюда следует, что Ье < Ь| + 1, Ь| < Ьг+ 1, ..., Ьм ~ < Ьо+ 1. На третьем уровне сортируем ((1с, а, Ь) ] 0 < о, Ь < т] при 0 < Й < иц число единиц в Ь-й группе тогда будет таким: ~ ~~В +Ь !./] Если 0 < осы < т~, имеем сь < ( ') и се = О при у' < Е Лнвлогкчно, если 0 < сь < тт, имеем се+~ > шз-(м, ') и сз = 0 при у > 5+1. Следовательно четвертый уровень который сортирует линии ш"Ь вЂ” ( ') ..ш"Й+ (~ ') — 1 при 0 < й < ш, завершит сортировку.
Из всего сказанного следует, что четыре уровня из ш-звементных сортировщиков рассортируют /(щ) = (~/ш]з элементов, а 16 уровней. рассортируют /(/(гл)) злементов. Это доказывает исходное утверждение, поскольку /(/(ш)) > т~, когда т > 24. (Описанное построение не относится к '"компактным", так что, возможно, вам удастси достичь того же результата и с меньшим числом уровней.) 55.
]Если Р(п) обозначает минимальное чигло переключателей, необходимых в перестановочной сети, то ясно, что Р(п) > (13 и(]. Несколько изменив построение, как предлагается в работе 1,. Х. Со1с(- щеш, Я. Ж, 1.е)ЬЬо1г, 1ЕЕЕ Тгапз. ЕС-16 (1967), 637 — 641, можно показать, что Р(п) < Р((п/2]) + Р((п/2]) + и — 1.
Следовательно, Р(п) < В(и) для всех и, где В(п) есть функция двоичной вставки нз 5.3.1-(3). М, У, Грин (М. ЪЧ. Сгееп) показал, что Р(5) = 3.] 56. Можно построить ов по индукции так, что яа„= Оь 101" ь, если я имеет Ь нулей. Основной случай, а~е — вырожденный. Иначе применяется, по крайней мере, один из следующих четырех случаев, где у не рассортировано; (1) я = 90, а, от]п-1:п]]п-2:и — 1]...]1:2]. (2) х = у1, а = от(1:п]]2:и]...]и — 1:и]. (3) х = 09, о а„+]1:п]]1;и — 11...
]1; 2]. (4) х = 19, о, = от ]1:2]]2:3]... ]и — 1:и]. Сеть ае получается ива в результате замены каждого компаратора ]1:у] компаратором ]1+1:у +1]. ]См. М. Л. СЬппй, В. Ватйпшаг, 111зсгесе Маей. 81 (1990), 1 — 9.] В втой конструкции используется (") — 1 компараторов; а можно ли достичь того же результата с существенно меньшим числом компараторов? 57.
[См. Н, Ейп, Гс. ЯеббевйсЬ, АТОС 14 (1982), 296-302.] Указанное время задержки легко проверяется по индукции., ио проблема анализа рекуррентного соотношения А(т, и) = А((ш/2], ]и/2] ) + А((т/2], (и/2]) + (гл/21 + ]и/2] — 1, когда А(0, и) = А(т,0) = О, более сложна. В процессе битонного слияния выполняется В(ш, и) = С'(т+ и) сравнений (см. (15)). Таким образом, можно использовать то, что ((т/2] + (и/21 (гл/2] + (п/2]) = (((ел + и)/2], ((гл + и)/2] ), чтобы показать, что В(ш, и) = В((гл/2], (и/2]) + В((т/2], (и/2]) + '((т+и)/2]. Тогда по индукции А(т,п) < В(т,п). Пусть В(ш,п) = С(т+1,я+1)+С(т,п) — С(т+1,п) — С(т, и+1).
Имеем В(0, и) = Р(эи,0) = 1 и 11(т, и) = 1, когда ш+ и нечетно. В противном случае ш+ и четио, глп > 1 и имеем В(т, и) = В((ш/2], (и/2]) — 1. Следовательно, 11(т, и) < 1 при всех ш, и > О. Рекуррентное соотношение для А зквивалентно рекуррентному соотношению для С, за исключением случая, когда оба параметра — и т, и и — нечетиы. Но и в атом случае имеем А(ш, и) > С((ш/2], (и/2]) + С((ш/2], (и/2]) + ] гл/2] + (и/2] — 1 = С(т, и) + 1— )У((ш/2], (и/2]) > С(ш, и) по индукции. Пусть 1 = (16 ш1п(т, и)]. На уровне Ь четно-нечетной рекурсии при О < Ь < 1 выполняем 2" глияний соответствующих размеров (туюпзь) = (((т+у)/2"], ((и+ 2 — 1 — у)/2 ]) при 0 < у < 2е.
Цена рекурсии, ): ((шдь/2] + (пзь/2] — 1), есть /ь(т) + /ь(п) — 2ь~ можно записать /ь(п) = !пах(п'„, н — сс»), где и'„= 2ь[и/2ьэ! + 1/2] кратно 2", ближайшему к и/2. Поскольку О < /ь(п) — и/2 < 2ь-с, суммарная цена рекурсии для уровней от 0 до ! — 1 лежит между с(сл+ п)1 — 2' и —.'(гн+ и)!. Наконец, если т < и, то 2' слияний (т»с, л»!) на уровне ! имеют сн;! = 0 при О < У < 2 — т и т»! = 1 — при других значениях т из/р Поскольку А(1,п) = и, суммарная цена ! уровня ! равна 2~ ~," '[й/2'] < ~„,",'~ ' й/т = ~ ! + и.
Таким образом, четно-нечетное слияние, в отличие от битонного слияния, характеризуется О(т + и) оптииалыюго числа сравнений М(т, и). Наши рассуждения покиэьсвают фактически, что А(гп, и) = 2 ! '„(/ь(гп) + /ь(п) — 21) + рс(т+ и) — дс(шах(па, и)), !де ус(п) можно представить в форме 2 ".,', [й/2с] = (и/2с](п — 2! '([н/2 ] + 1)). 58. Если Ь[й + Ц ж Ь[й) + 1 и файл еще не упорядочен, то иа следующем проходе с ним обязательно произойдут какие-нибудь изменения.
Как показано в упр. 5.2.2-1, число инверсий уменьшится и, следовательно, файл, в конце концов, рассортируется. Но если И[И + Ц > Ь[й] + 2 при 1 < [с < т, то наименьший ключ никогда не попадает в нужное место, если он первоначально находится в Йэ. 59. Используем указание и рассмотрим следующий случай; Кн+! = Кнеэ = .. = 1. Если Кь[с[э!. = . =- Кь[ [ь! и 1 на шаге у и если К; = 0 при некотором с > И[Ц + /л то должно оказаться с < И[т) + 1, так как число единиц не превышает и. Предположим, что й и с минимальные, такие, что Ь[й) + у < с < Ь[й+ Ц + ! и К, = О, Пусть з = И[И+ Ц +,1 — с; имеем з < Ь[й+ Ц вЂ” И[[с) < й. На шаге у — з под головками должно быть, по крайней иере, й+ 1 нулей, так как К, = Кэ[ьэс[э», устанавливается равным нулю на этом шаге; еще через з шагов между Кь[с[э„и К; включительно остается не менее И+ 1 — з > 2 нулей, что противоречит минимальности с.
При втором проходе следующие и — 1 элементов помещаются на свои места и т, д, Если мы начинаем с перестановки Ь[ Ь[ — 1 ... 2 1, то при первом проходе она принимает внд Ьс+1-и Ж-и ... 1 И[+2-и ... !с! — 1 !»!, поскольку Кмц+! > Кь[„,1+! всякий рэз, когда 1 < Ь[Ц + у и Ь[т) + у < Ю; следовательно, приведенная оценка является наилучшей из возможных.
50. Предположим, что Ь[й+ Ц вЂ” з > Ь[й] и Ь[й] < з; если наименьший ключ вначале находился в позиции Л„„то, в конце концов, он окажется в позиции 2!! при с > 1. Следовательно, условие Ь[й+ Ц < 2Ь[й] является необходимым; оно также является достаточным в частном случае, при 1 = О, следующей теоремы. Теорема. Если и = Ф, а Л!... Кн — перестановка множества (1, 2,..., и), то прн одном проходе сортировки будет установлено К! = с при 1 < с < с+1, если Ь[й+ Ц < Ь[й)+!»[й-с]+! прн 1 < й < »и н О < с < 1. (Условимся, что Ь[й] = й, если й < О.) Доказоглезьстзз.
Применяем индукцию по !. Если на шаге ! ключ ! + 1 не находится под головками, то можно считать, что он расположен в позиции !!ь[ь»бэс-» п1»н некоторо»с з > О, где !с[й + Ц вЂ” з < Ь[й]; следовательно, И[И вЂ” с) + ! — з > О. Но это невозможно, если рассмотреть шаг ! — з, на которои, вероятно, элемент 1+ 1 был помещен в позицию Яь[ь~.с[э! „хотя имелись, по крайней мере, С+ 1 иеныпих активных головок. $ (Это ушсовие необходимо при ! = О, 1, но не при ! = 2.) 51, Если сортируются числа (1,...,23), то в соответствии с теоремой пэ предыдущего упражнения получаем, что (1, 2, 3, 4] попадают на свои окоичательньсе места.
Можно проверить„что в случае сортировки нулей и единиц на шагах — 2, -1 и О невозможно такое по»южение, когда все головки читают О, а во всех позициях не под головками содержится 1; следовательно, докэзательство в предыдущем упражнении можно расширить и, таким образом, показать, что (5, 6, 7) также попадают на свои места. Наконец, то, что (8,...,23) должны сортироваться, следует из рассуждений, приведенных в упр. 59. 63. Если г < ш — 2, то головки преобразуют цепочку 0" 1'01 О! О... 01~ '01" в цепочку Ог+'!'О!э01г0...01т '01з 'еэ; следовательно, необходимо ш — 2 проходов. !Для случая, когда головки находятся в позициях 1,2,3,5,...,1 + 2 э,Пратт получил аналоэьэ 1 гичный результат: цепочка Ог!'О1 '01 '0... 01э '01", 1 < а < 2" ', превращается в за ~ ээ Ог+'!' '01з '01э '0 ...
01т '01э ~~; значит, для такой последовательности головок в наихудшем случае требуется не менее т — !"!обе т] — 1 проходов. Эта последовательность головок особенно интересна, поскольку она была использована как основа весьма остроумного сортирующего устройства, изобретенного Ф. Н. Армстронгом (Р. Х.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
