Класс (а) должен содержать, по крайней мере, М{п, п) компараторов, так как Z2n+i, 2п+2, , Z4n могут уже находиться на своих местах, когда слияние начинается; аналогично в классе (Ь) должно быть хотя бы М(п, п) компараторов. Кроме того, как показывает входная последовательность (0,1,0,1,.. .,0,1), класс (с) содержит не менее п компараторов, так как п нулей должны переместиться из {z2n+i, , Z4n)

в {zi,...,Z2„). I

Многократное применение теоремы F доказывает, что М{2", 2™) > (т + 2)2"; следовательно, М{п,п) > nlgn+ 0{п). Из теоремы 5.3.2М известно, что слияние без сетевого ограничения требует лишь М{п,п) - 2п-1 сравнений; таким образом, мы доказали, что сетевое слияние сложнее по существу, чем слияние вообще.

Четно-нечетное слияние показывает, что

М{т,п) < С{т,п) = (т -f- п) Igmin(m,n) -f- 0{т + п).

В работе Р. В. Miltersen, М. Paterson, J. Tarui, JACM 43 (1996), 147-165, теорема F доработана и установлена нижняя оценка

М{т,п) > ((т -f- п) lg(m -f-1) - тп/In2) при 1 < m < п.

Следовательно, М{т,п) = (т + п) Igmin(m,п) + 0{т + п).

Точная формула М{2, п) = С(2, п) = [п] доказана в работе А. С. Yao, F. F. Yao, JACM 23 (1976), 566-571. Также известно, что значение М{т,п) равно С{т,п) для т = п < 5 [см. упр. 9].

Битонная сортировка. Если допустимы одновременные сравнения, то, как видно из формулы (12), при четно-нечетном слиянии для I < т < п возникает задержка на [lg(2n)] единиц времени. Бэтчер изобрел другой тип сети слияния, названный битонным сортировщиком (bitonic sorter)*, для которого время задержки снижается до [lg(m + п)]. Но он требует больше модулей компараторов. [См. U.S. Patent 3428946 (1969).]

Последовательность (zi,..., Zp) из р чисел будем называть битонной, если zi > Zk < • < Zp для некоторого к, 1 < к < р. (Сравните это с обычным определением "монотонных" последовательностей.) Битонный сортировщик порядка р - это сеть компараторов, способная сортировать в порядке неубывания любую битонную последовательность длиной р. Задача слияния Xi < < Хт с 2/1 < " < Уп является частным случаем задачи битонной сортировки, так как слияние можно осуществить, применив к последовательности (хт,..., ai, j/i,..., Уп) битонный сортировщик порядка т + п.

Заметим, что если последовательность {zi,...,Zp) битонная, то таковыми же являются и все ее подпоследовательности. Вскоре после того, как Бэтчер открыл сети четно-нечетного слияния, он обнаружил, что аналогичным образом можно построить битонный сортировщик порядка р, сначала независимо сортируя битонные подпоследовательности (zi, zz, z,...) и {z2, z4, zq, ), a затем выполняя сравнения-обмены Zi:z2, Z3:z4, ... . (Доказательство приводится в упр. 10.) Если соответству-

* Термин "битонная последовательность" (bitonic sequence) введен по аналогии с термином "монотонная последовательность" (monotonic sequence). - Прим. перев.

21 - Z2 -

23 -

24 -

Zb -

26 -

27 -

Рис. 52. Битонный сортировщик Бэтчера порядка 7.

ющее число модулей компараторов обозначить через С(р), то будем иметь

C(p)=C(b/2l)+C(b/2J) + b/2j прир>2; (15)

а время задержки, очевидно, равно [Igp]- На рис. 52 показан битонный сортировщик порядка 7, построенный этим способом; он может быть использован и как (3, 4)-, и как (2, 5)-сеть слияния с задержкой в три единицы; четно-нечетное слияние для m = 2 и п = 5 имеет на один компаратор меньше, но на один уровень задержки больше.

Особый интерес представляет битонный сортировщик Бэтчера порядка 2; он состоит из t уровней по 2 компараторов в каждом. Пронумеруем входные линии zo,zi,... ,Z2t-i; при этом элемент Zi сравнивается с Zj на уровне I тогда и только тогда, когда двоичные представления г и j различаются только в 1-м слева разряде. Эта простая структура приводит к созданию параллельной сети сортировки, которая функционирует так же быстро, как обменная сортировка со слиянием (алгоритм 5.2.2М), но реализовать ее значительно проще (см. упр. 11 и 13).

Битонная сортировка оптимальна в том смысле, что ни один метод параллельного слияния, основанный на одновременно несвязанных сравнениях, не может выполнять сортировку быстрее, чем за lg(m + п)] стадий, независимо от того, используется ли при этом предыстория (см. упр. 46). Существует и другой способ достижения оптимума, который требует меньше сравнений, но логика его чуть сложнее. Этот метод анализируется в упр. 57.

Если 1 < m < п, то п-й (считая от наименьшего) выход (т,п)-сети слияния должен зависеть от 2т -\-[т<п] входов (см. упр. 29). Если его можно вычислить, используя компараторы с I уровнями задержки, то в результат будет вовлечено не более 2 входов; следовательно, 2 > 2т -f- [т < п] и I > [lg(2m -Ь [m < п])]. Бэтчер показал [Report GER-14122 (Akron, Ohio: Goodyear Aerospace Corporation, 1968)], что это минимальное время задержки достигается, если в сети допускается разветвление, т. е. такое разбиение линий, что одно и то же число в одно и то же время используется несколькими модулями. В качестве примера на рис. 53 изображена сеть (п = б), которая сливает один элемент с п другими после всего двух уровней задержки. Конечно, сети с разветвлением не соответствуют нашим соглашениям; довольно легко понять, что любая (1,п)-сеть слияния без разветвления должна иметь время задержки lg(n + 1) или более (см. упр. 45).

Сети выбора. Сети можно применить также к задаче раздела 5.3.3. Пусть Ut{n) обозначает минимальное число компараторов, необходимых в сети, которая перемещает t наибольших из п различных входов на t определенных выходных линий; они могут располагаться на этих выходных линиях в произвольном порядке. Пусть Vt{n) обозначает минимальное количество компараторов, необходимых для перемещения

У2 уз

УЬ Уб

21 • 2

Zb

Zb

z-r

Рис. 53. Сеть, обеспечивающая слияние одного элемента с шестью другими и имеющая разветвления, в результате чего достигается минимальная задержка.

*-го входа в порядке убывания из п различных входов на определенную выходную линию, и пусть Wt{n) обозначает минимальное число компараторов, требуемых для перемещения t наибольших из п различных входов на определенные t выходные линии в порядке неубывания. Нетрудно видеть (см. упр. 17), что

l}t{n) < Vt{n) < Wt{n). (16)

Сначала предположим, что имеется 2t элементов {xi,... ,X2t) и мы хотим выбрать t наибольших. В. Е. Алексеев [Кибернетика 5, 5 (1969), 99-103] заметил, что это .может быть выполнено, если сначала рассортировать {хг,... ,xt) и {xt+i,..., X2t), а затем сравнить и поменять местами

Xi:x2t, X2:x2t-i, xt.xt+i. (17)

Так как ни в одной из этих пар не может содержаться более одного из наибольших t элементов (почему?), процедура Алексеева должна выбрать t наибольших элементов.

Если нужно выбрать t наибольших из nt элементов, то мы можем применить эту процедуру п - 1 раз (исключая каждый раз t элементов); следовательно,

Utint) <{n-l){2S{t) + t). (18)

Алексеев также получил интересную нижнюю оценку для задачи выбора.

Теорема А. С7<(п) >{n-t) \\g{t + 1) .

Доказательство. Удобнее рассматривать эквивалентную задачу выбора наименьших t элементов. Около каждой линии сети компараторов можно выписать числа {1,и), как показано на рис. 54, где I и и обозначают соответственно минимальное и максимальное значения, которые могут появиться в этом месте, если входом служит перестановка {1,2, ...,п}. Пусть 1, и Ij - нижние оценки на прямых i и j перед сравнением Xi: Xj и пусть 1 и Ij - соответствующие нижние оценки после этого сравнения. Очевидно, что Ц = min{l,lj), а в упр. 24 доказывается соотношение (неочевидное)

<li + ly (19)