AOP_Tom3 (1021738), страница 190
Текст из файла (страница 190)
Первый уровень сортирует линии ((а, Ь, (Ь+ )с) и!ос! т) [ 0 < а,Ь < сп) при О < й < т; пусть ао — число единиц в Ь-й группе из тг линий. Второй уровень сортирует [(а, Ь, .1о) [ 0 < а, Ь < т) при 0 < Ь < т; число единиц в Ь-й группе тогда будет таким: и отсюда следует, что Ьс < Ь| + 1, Ь| < Ьз + 1, ..., Ь ~ < Ьо + 1.
На третьем уровне сортируем ((Ьца., Ь) [ 0 < а, Ь < т) при 0 < Ь < т; число единиц в?с-й группе тогда будет Если 0 < сь ~~ < т~, имеем сь < (, ) н сз — — 0 при / < Е Аналогично, если 0 < сь < т~, — ! имеем ссэл > т — ("' ') и сз = 0 при/ > 5+1. Следовательно, четвертый уровень, который сортирует линии т~1 — ( ') .. гп Й+ ( ') — 1 при 0 < Ь < т, завершит сортировку. Из всего сказанного следует, чта четыре уровня из ги-элементных сортировщиков рассортируют /(т) = [ь/т]з элементов, а 1б уровней рассортируют /(/(т)) элементов.
Это доказывает исходное утверждение. поскольку /(/(т)) > т~, когда т > 24. (Описанное построение не относится к "компактным", так что, возможно, вам удастся достичь того же результата и с меньшим числом уровней.) 55. [Если Р(и) обозна эаст минимальное число переключателей, необходимых в перестановочной сети, то ясно, что Р(и) > [!б и)]. Несколько изменив построение, как предлагается в работе Ц Л. Со)С- зсе!и, Я.
Ч'. Ье~ЬЬо!х, ?ЕЕЕ 2?алз. ЕС-16 (1967), 637 — 641, можно показать, что Р(и) < Р([и/2] ) + Р()и/2] ) + и — 1. Следовательно, Р(и) < В(и) для всех и, где В(и) есть функция двоичной вставки из 5.3.1 — (3). М. У. Грин (М. %. Сгееп) показал, что Р(5) = 8.] 56. Можно построить о, по индукции так. чта хо = 0 101", если х имеет !Г нулей. Основной случай, о~с — вырожденный. Иначе применяется, по крайней мере, один из следующих четырех случаев, где у не рассортировано: (1) х = уО, и, а„[и-1:и][и — 2:и-1]...
[1:2]. (2) х = у1, о = а„[1:и][2:и]...[и-1:и]. (3) х = Оу, а„= о~[1.иИ1:и — 1]... [1:2]. (4) х = 1у, а = аг [1:2][2:3]... [и — 1:и]. Сеть ос получается из о в результате замены каждого компаратора [1:/] компаратором [г +1:/-?1]. [См. М. Л. СЬпаб, В. 1?атйшпаг, В!эсгесе Ьйагб. 61 (1990), 1-9.] В этой конструкции используется (") — 1 компараторов: а можно ли достичь того же результата с существенно меньшим числом компараторав? 57. [См. Н. 2Ьп, Гс Яейбеебс?, АТОС 14 (1982), 296 — 302,] Указанное время задержки легко проверяется по инлукции,на проблема анализа рекуррентнога соотношения А(т„и) = А([ги/2], [и/2]) 4- А([т/2], [и/2]) + [т/2] + [и/2] — 1, когда А(0,.
и) = А(ги., О) = О, более сложна. В процессе битанного слияния выполняется В(т, и) = С'(ги+ и) сравнений (см. (15)). Таким образом, можно использовать то, что ((т/2] + [и/2], [т/2] + [и/2]) = ([(т + п)/2], Ит -? и)/2]), чтобы показать. что В(т, и) = В([т/2], [и/2]) + В([ти/2], (и/2]) + [(т+ и)/2]. Тогда гю индукции А(т, и) < В(т, и). Пусть В(т, и) = С(т+ 1, и+ 1) + С(т, и) — С(т+ 1, и) — С(т, п+ 1). Имеем В(0, и) = В(т, О) = 1 и В(т, п) = 1, когда т+ и нечетно.
В противном случае т+ п четно, гии > 1 и имеем В(т, п) = В((т/2], [и/2]) — 1. Следовательно, В(т, и) < 1 при всех т, и > О. Рекуррентное соотношение для А эквивалентно рекуррентному соотношению длн С, за исключением случаи, когда оба параметра — и т, и и — нечетны. Но и в этом случае имеем А(ги, га) > С( т/2], [и/2]) + С([т/2], [и/2]) + [т/2] + [и/2] — 1 = С(гп, и) + 1— В([т/2], [и/2]) > С(т, и) по индукции. Нусть ! = [!б ппп(т, ии На уровне 1 четно-нечетной рекурсии при 0 < !г < ! выполняем 2" слияний соответствующих размеров (тем из ь) = ( [(т+ /)/2ь], Ии+ 2" — 1 — /)/2~]) пРи 0 < / < 2".
Цена РекУРсии, 2, ([тзь/2] + [им/2] — 1), есть /ь(т) + /ь(и) — 2"; можно записать /с (и) = шах(пы и — и'„), где и'„= 2ь [и/2вж' + 1/2] кратно 2в, ближайшему к и/2. Поскольку О < /с(п) — и/2 < 2"-', сулсмарная цена рекурсии для уровней от О до 1 — 1 лежит между -'(т+ п)1 — 2' и -'(т+ и)1. Наконец, если си < и, то 2' слияний (т,с, п,с) на уровне 1 имеют т,с = О при О < 1 < 2 — гп н т,с = 1 — прн других значениях т из г.
Поскольку А(1, и) = и, суммарная цена с УРовнЯ 1 Равна 2 в „" [Й/2'] < 2 „+„" ' 1с/т = ='+ п, Таким образом,четно-нечетное глияние, в отличие от битонного слияния, характеризуется 0(т+ и) оптимального чнгла сравнений М(пс,п). Наши рассуждения показывают фактически, что А(т,п) = 2 'е(/в(т) +/в(п) — 2 ) +дс(т+п) — дс(ссгах(т,сс)), где дс(п) можно представить в форме 2 „",, '[Ь/2'] = [п/2с](п — 2' '([п/2'] + 1)). бб. Если 6[6 + Ц = 6[6] + 1 и файл еще не упорядочен, то на следующем проходе с ним обязательна произойдут какие-нибудь изменения.
Как показано в упр. 5.2.2 — 1, число инверсий уменьшится и, следовательно, файл, в конце концов, рассортируется. Но если 6[6 -с- Ц > 6[6] + 2 при 1 < 1с < т, то наименьший ключ никогда не попадает в нужное место, если он первоначально находится в Кг. 59. Используем указание и рассмотрим слегсуюсций случай: Ккег = Кквг = = 1. Если Кл1г1ьг = ' = Кл1 рю — — 1 на шаге / н если К, = О прн некотором с > 6[Ц+ 1, то должно оказаться с < 6[си] + /и так как число единиц не превышает п.
Предположим, что 6 и с минимальные, такие, что 6[6] -Ь г < с < 6[й Ч- Ц + г и Кс = О. Пусть в = 6[1с ч- Ц +,у — с; имеем в < 6[6 + Ц вЂ” 6[6] < Ь. На шаге / — в под геленками должно быть, по крайней мере, 6 + 1 нулей., так как К, = Кь1с+Осг, устанавливается равным нулю на этом шаге; еще через в шагов между Кь1г1+ н К, включительна остается не менее й+ 1 — в > 2 нулей, что противоречит минимальности с. При втором проходе следующие и — 1 элементов помещаются на свои места и т.
д. Если мы начинаем с перестановки Х Х-1 ... 2 1, та при первом проходе она принимает внд /с1+1 — п 1г — и ... 1 %+2 — и ... Ьс-1 Ьс, посколькУ Кь1с,~.г > Кь1„1ег всЯкий Раз, когда 1 < 6[Ц + 1' и 6[т] +/ < Х; следовательно, приведенная оценка является наилучшей из возможных. ВО. Предположим, чта 6(6 + Ц вЂ” в > 6[й] и 6(6] < з; если наименьший ключ вначале находился в позиции К„„то, в конце концов, он окажется в позиции Н„при с > 1. Следовательно, условие 6[6+ Ц < 26[6] является необходимым; оно также является достаточным в частном случае, при 1 = О, следующей теоремы.
Теорема. Если и = гУ, а Кг ... Кк — перестановка множества (1, 2,..., п), то пря одном проходе сортировки будетустановлено К = с пря 1 < с < 1Ч-1, если 6[6+Ц < 6[6]+6[6 — с)+с пря 1 < 6 < т и О < с < и (Угловнмся, чта 6[6] = 6, если Ь < О ) Доказательства.
Прнменяелс индукцию по 6 Если на шаге 1 ключ в + 1 не находится под головками, то можно счнтатеч чта он расположен в позиции Нь1в.сг1+с, при некотором з > О, где 6[1с + Ц вЂ” з < 6[1с); гледавательно, 6[1с — 1] + 1 — в > О. Но это невозможно, сели рассмотреть шаг 1 — з, на котором, вероятно, элемент 1+ 1 был помещен в позицию Кв1вэс1эс „хата имелись, по крайней мере, 1+ 1 меньших активных головок. ) (Это условие необходима при 1 = О, 1, но не при 1 = 2.) 91.
Егли сортируются числа (1,..., 23), та в соответствии с теоремой из предыдущего упражнения получаем, что (1, 2,3,4» попадают на свои окончательные места. Можно проверить, что в случае сортировки нулей и единиц на шагах — 2, -1 н О невозможно такое положение, когда все головки читают О, а во всех позициях не под головками содержится 1; следовательно, доказательства в предыдущем упражнении можно расширить и, таким образом, показать, что (5, б, 7) также попадают на свои места. Наконец, то, что (8,..., 23) должны сортироваться, следует из рассуждений, приведенных в упр. 59. 63.
Если г < ьп — 2, то головки преобразуют цепочку Ог1'01 0110...011 '011 в цепочку 0" "'1'01101 0 ., 011 '011 '" г; следовательно, необходима пь — 2 проходов. (Для случая, когда головки находятся в позициях 1,2,3,5, ,1 + 2 г, Пратт получил аншюггьь гичный результат: цепочка Ог1'01 '01 '0 .. 011 '011, 1 < а < 2 ', превращается в 1 а-1 гь 1 гьэ1-1 г" '-1 г" Эь Оье'1'-'011 '011 'О .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
