j=0 L

a(k-j) mod m + J m2

[1 + 2п:2тп + 2п+ 1][3 + 2п:2тп + 2п+ 1][6 + 2п:2тп + 2п + 1]

[4 + 4п:2тп + 2п + 2][5 + 4п:2тп + 2п + 2][8 + 4п:2тп + 2п + 2]...,

если использовать X2j-i+2kn и X2j+2kn ДЛЯ представления yj а yj в к-м подвыражении и Х2т+2п+к - ДЛЯ представления самого этого выражения.

53. Раскрасьте все линии красным или синим цветом в соответствии со следующим правилом:

если г mod 4 равно тогда цвет линии г в случае (а) цвет в случае (Ь)

0 красный красный

1 синий красный

2 синий синий

3 красный синий

Теперь вы увидите, что первые t - 1 уровней сети состоят из двух отдельных сетей: одна из 2" красных линий, а другая - из 2~ синих линий. Компараторы на t-м уровне образуют сеть слияния, как в сетях битонного или четно-нечетного слияния. Таким образом, мы получили искомый результат при к = 1.

Красно-синяя декомпозиция также годится и для случая к = 2. Если вход 4-упорядо-чен, красные линии содержат 2~ чисел, которые являются 2-упорядоченными; то же самое можно сказать относительно синих линий. Так что мы оказались в ситуации с

Х0У0У1Х1Х2У2У3Х3 (случай (а)) или хоХ1уоу1Х2Хзу2Уз (случай (Ь))

после t - 1 уровней; окончательный результат

(a;oAyo)(a;oVyo)(yiAa;i)(yiVxi)... или xo(xiAyo)(a;iVyo)(yiAx2)(yi Ужг)...

совершенно очевидно является 2-упорядоченным.

Теперь для к > 2 можно предположить, что к < t. Первые t - k + 2 уровней разделяются в результате декомпозиции на 2*" отдельных сетей размером 2~*+, каждая из которых является 2-упорядоченной в случае к = 2; следовательно, линии являются 2*"-упорядоченными после t - k + 2 уровней. Последующие уровни, очевидно, сохраняют 2*""-упорядочение, поскольку они обладают "вертикальной" периодичностью порядка 2*". (Можно представить себе -оо на линиях -1, -2, ... и +оо - на линиях 2, 2 + 1,----)

Литефатура. Сеть (а) впервые была рассмотрена в работе М. Dowd, Y. Perl, L. Rudolph, М. Saks, JACM 36 (1989), 738-757; сеть (b) - в работе E. R. Canfield, S. G. Williamson, Linear and Multilinear Algebra 29 (1991), 43-51. Интересно отметить, что в случая (а) имеем Dna = Gt, где Gt определено в упр. 32 [Дауд и др., теорема 17]; таким образом, изображения Dn самого по себе недостаточно для того, чтобы охарактеризовать поведение периодической сети.

54. Следующее построение выполнено в работе Ajtai, Komlos, Szemeredi [FOCS 33 (1992), 686-692]. Оно показывает, как рассортировать элементов с четырьмя уровнями т-элементных сортировщиков: предположим, что сортируемые элементы суть нули и единицы; пронумеруем линии (а,6,с) = ат + Ьт + с при Q < а,Ь,с < т. Первый уровень сортирует линии {(а,6, (6 + к) mod т) \ Q < а,Ь < т} при Q < к < т; пусть ак - число единиц в к-п группе из линий. Второй уровень сортирует {[а,Ь,к) О < а,6 < т} при Q <к < т; число единиц в к-п группе тогда будет таким:

и отсюда следует, что Ьо < bi + 1, bi < Ьг + 1, • , bm-i < Ьо + 1- На третьем уровне сортируем {{к,а,Ь) \ О < а,Ь < тп} при О < к < тп; число единиц в к-й группе тогда будет таким:

т-1т-1 , , , ,

EV- Ь, + km + J 2- -т-

г=0 j=0 I

Если О < Ск+1 < т, имеем Ск < (""j) и Cj = О при j < к. Аналогично, если О < Ск < т, имеем Cfc+i > пг-("~) и Cj = Опри > к+1. Следовательно, четвертый уровень, который сортирует линии тк - (""J) • • тк + (""j) - 1 при О < к < т, завершит сортировку.

Из всего сказанного следует, что четыре уровня из т-элементных сортировщиков рассортируют /(т) = [у/т элементов, а 16 уровней рассортируют f{f{m)) элементов. Это доказывает исходное утверждение, поскольку f{f{m)) > т, когда m > 24. (Описанное построение не относится к "компактным", так что, возможно, вам удастся достичь того же результата и с меньшим числом уровней.)

55. т [Если Р(п) обозначает минимальное число переключателей, необ-

- ходимых в перестановочной сети, то ясно, что Р{п) > [Ign!]. Не-

- сколько изменив построение, как предлагается в работе L. J. Gold-

- stein, S. W. Leibholz, IEEE Ъапз. EC-16 (1967), 637-641, можно показать, что P(n) < P([n/2J) +P([n/2]) + n- 1. Следовательно,

P(n) < B{n) для всех n, где В{п) есть функция двоичной вставки из 5.3.1-(3). М. У. Грин (М. W. Green) показал, что Р(5) = 8.)

56. Можно построить Ох по индукции так, что ха = OlOl""*", если х имеет к нулей. Основной случай, аю - вырожденный. Иначе применяется, по крайней мере, один из следующих четырех случаев, где у не рассортировано: (1) х = уО, Ох = aj,[n-l:n][n-2:n-l]...[l:2]. (2) х = у1, Ох = aj,[l :п][2: п]... [п-1 :п]. (3) х = Оу, Ох = а+[1:п][1:п-1]... [1:2]. (4) х = 1у, a. = а+[1:2][2:3] . .. [п-1:п]. Сеть а+ получается из а в результате замены каждого компаратора компаратором [i-bl:j4-l]. [См. М. J. Chung, В. Ravilfumar, Discrete Math. 81 (1990), 1-9.] В этой конструкции используется {) - 1 компараторов; а можно ли достичь того же результата с существенно меньшим числом компараторов?

57. [См. Н. Zhu, R. Sedgewicl£, STOC 14 (1982), 296-302.] Указанное время задержки легко проверяется по индукции, но проблема анализа рекуррентного соотношения

А{т,п) A([m/2J, [п/2]) + А([т/2], [n/2j) + [m/2] + [n/2] - 1,

когда А(0, п) = А{т, 0) = О, более сложна.

В процессе битонного слияния выполняется В{т,п) = С[т + п) сравнений (см. (15)). Таким образом, можно использовать то, что {[m/2j + [п/2], [т/2] + [n/2j} = {[(m + n)/2J, [(m + n)/2]}, чтобы показать, что В{т,п) = S([m/2J, [n/2]) -I- B([m/2], [n/2J) + [(m + n)/2j. Тогда no индукции A(m,n) < B{m,n).

Пусть D(m,n) = C(m + l,n+l) + C(m,n)-C(m + l,n)-C(m,n+l). Имеем D(0,n) = D{m, 0) = 1 и D(m, n) - 1, когда m + n нечетно. В противном случае т + п четно, ттг > 1 и имеем D{m,n) = D([m/2J, [n/2J) - 1. Следовательно, D{m,n) < 1 при всех m,n > 0.

Рекуррентное соотношение для А эквивалентно рекуррентному соотношению для С, за исключением случая, когда оба параметра - и т, и п - нечетны. Но и в этом случае имеем А{т,п) > C([m/2J, [п/2]) + С([т/2], [n/2J) + [m/2] + [n/2] - 1 = C(m,n) + 1 -D{[m/2\, [n/2j) > C{m,n) no индукции.

Пусть / = [Ig min(m, n)]. Ha уровне к четно-нечетной рекурсии при О < к < I выполняем 2*" слияний соответствующих размеров {mjk,njk) = {\.{т+ j)l2\, [(п+ 2* - 1 - j)/2*J) при О < j < 2*. Цена рекурсии, Ej(r"jt/2] + [njfc/2] - 1), есть fk{m) + fk{n) - 2*; можно

записать fk{n) = тгх.{щ,п - щ), где п = 2*[n/2+i + 1/2J кратно 2*, ближайшему к п/2. Поскольку О < /fc(n) - п/2 < 2*-i, суммарная цена рекурсии для уровней от О до / - 1 лежит между (т + п)1 - 2 и {т + п)1.

Наконец, если m < п, то 2 слияний {niji, riji) на уровне I имеют тпц = О при О < j < 2 - m и niji = 1 - при других значениях m из j. Поскольку А{1, п) = п, суммарная цена уровня I равна Er=„""4V2j < ЕГ=п" к/т+ п.

Таким образом, четно-нечетное слияние, в отличие от битонного слияния, характеризуется 0(т + п) оптимального числа сравнений М(т, п). Наши рассуждения показывают фактически, что А{т, п) = El=o(/t(") + ~ 2*) + gi{m + п) - з;(тах(т, п)), где s;(n) можно представить в форме f2lZo[k/2\ = [п/2](п - 2-{[п/2] + 1)).

58. Если h[k + 1] = h[k] + 1 а файл еще не упорядочен, то на следующем проходе с ним обязательно произойдут какие-нибудь изменения. Как показано в упр. 5.2.2-1, число инверсий уменьшится и, следовательно, файл, в конце концов, рассортируется. Но если h[k + 1] > h[k] + 2 при 1 < А; < m, то наименьший ключ никогда не попадает в нужное место, если он первоначально находится в R2.

59. Используем указание и рассмотрим следующий случай: Kn+i = Kn+2 = • = 1. Если h[i]+j = = Kh[m]+j = 1 на шаге j и если Kt = О при некотором г > h[l] + j, то должно оказаться г < h[m] + j, так как число единиц не превышает п. Предположим, что к ш i минимальные, такие, что h[k] + j < i < h[k + 1] + j a Ki =0. Пусть s = h[k + 1] -I- j - г; имеем s < h[k -t-1] - h[k] < k. Ha шаге j - s под головками должно быть, по крайней мере, к + 1 нулей, так как Ki = устанавливается равным нулю на этом шаге; еще через S шагов между ATiij+j и Ki включительно остается не менее к+1 - s>2 нулей, что противоречит минимальности г.

При втором проходе следующие п - 1 элементов помещаются на свои места и т. д. Если мы начинаем с перестановки N N-1 ... 2 1, то при первом проходе она принимает вид

N+1-n N-n ... 1 iV+2-n ... N-1 N,

поскольку Kh[i]+j > Kh[m]+j всякий раз, когда 1 < h[l] -I-j и h[m] +j<N; следовательно, приведенная оценка является наилучшей из возможных.

60. Предположим, что h[k -t- 1] - s > h[k] и h[k] < s; если наименьший ключ вначале находился в позиции Rn-s, ТО, В конце концов, он окажется в позиции Ri при г > 1. Следовательно, условие /г[А;-Ь1] < 2h[k] является необходимым; оно также является достаточным в частном случае, при t = О, следующей теоремы.

Теорема. Если п = N, а Ki ... Kn - перестановка множества {1, 2,..., п}, то при одном проходе сортировки будет установлено Ki = гпри1 < г < t+1, еслиН[к+1] < h[k]+h[k-i]+i при 1 < к < т и О < i <t. (Условимся, что h[k] = к, если к < 0.)

Доказательство. Применяем индукцию по t. Если на шаге t ключ t -Ь 1 не находится под головками, то можно считать, что он расположен в позиции Rh[k+i]+t-s при некотором S > О, где h[k + 1] - S < h[k]; следовательно, h[k - t] + t - s > 0. Ho это невозможно, если рассмотреть шаг t - s, на котором, вероятно, элемент t + 1 был помещен в позицию Rh[k+i]+t-s, хотя имелись, по крайней мере, t+1 меньших активных головок.

(Это условие необходимо при t = 0,1, но не при t = 2.)

61. Если сортируются числа {1,...,23}, то в соответствии с теоремой из предыдущего упражнения получаем, что {1,2,3,4} попадают на свои окончательные места. Можно проверить, что в случае сортировки нулей и единиц на шагах -2, -1 и О невозможно такое положение, когда все головки читают О, а во всех позициях не под головками содержится 1; следовательно, доказательство в предыдущем упражнении можно расширить и, таким