дов &i, Ь2, , Ьп. При этом не может быть циклов: идя по проводам и проходя компараторы от входов к выходам, нельзя вернуться к исходному компаратору. Это требование позволяет рисовать сети компараторов в виде прямых, как на рисунке 28.2, располагая входы слева, а выходы справа: данные движутся по проводам слева направо.

Мы считаем, что каждый компаратор выдаёт выходные значения через единицу времени после того, как получит входные значения. Рассмотрим сеть рис. 28.2(a) и представим всебе, что в в момент времени 0 на вход поступают числа (9,5,2,6). В этот момент компараторы А и В (и только они) получают входные данные и начинают работать (параллельно). Поэтому в момент времени 1 на их выходах появятся числа (рис. 28.2(b)), которые позволят начать параллельную работу компараторам С и D (но не Е). Компаратору Е придётся дожидаться момента времени 2, когда С и D закончат работу (рис. 28.2(c)). Ещё через единицу времни выходная последовательность (2, 5, 6, 9) будет полностью готова (хотя два из четырёх значений были готовы раньше).

Как видно из этого примера, время работы сети (прошедшее с момента получения входной последовательности до выдачи выходной последовательности) определяется максимальным числом компараторов, стоящих на пути от входа к выходу. Более формально, мы определяем глубину (depth) провода в сети следующим образом: входные провода имеют нулевую глубину, глубина выходов компаратора (подключённых к нему проводов) равна max(dx, dy) + 1, где dx и dy - глубины его входов (подключённых к ним проводов). Это определение корректно, поскольку нет циклов. Назовем глубиной компаратора глубину выходящих из него проводов. Глубиной сети считаем максимальную глубину её выходных проводов (или, что то же самое, максимальную глубину её компараторов). Например, глубина сети на рисунке 28.2 равна 3 (компаратор Е имеет глубину 3). Глубина компаратора равна времени, которое пройдет от начала работы по появления ответов на его выходах, так что время работы сети в целом равно её глубине.

Размером (size) сети называют число компараторов в ней.

Любая сеть компараторов как-то переставляет числа, поданные на кё входы. Её называют сортирующей сетью (sorting network), если для любой входной последовательности получающаяся из неё выходная последовательность монотонно возрастает (h ь2 <С ••• <С Ьп).

Конечно, далеко не каждая сеть - сортирующая, но сеть рисунка 28.2 таковой является. В самом деле, в момент времени 1 минимальный из входов находится на верхнем выходе одного из компараторов А и В, и в момент времени 2 он кажется на на верхнем выходе компаратора С. Аналогичным образом максимальный из входов окажется в этот момент на нижнем выходе компарато-

Рис. 28.3 Сортирующая сеть, соответствующая сортировке вставками (упражнение 28.1-6).

pa D. Оставшиеся два числа упорядочиваются компаратором Е в момент времени 3.

Сети компараторов аналогичны алгоритмам сортировки, однако для каждого га мы должны строить свою сеть, в то время как один и тот жэе алгоритм сортировки может работать для последовательностей произвольной длины. В этой главе мы построим семейство Sorter эффективных сортирущих сетей - для каждого га в нём будет своя сеть, которую мы обозначаем SoRTER[ra].

Упражнения.

28.1-1

Каковы будут значения на проводах сети рис. 28.2, если на её вход подаются числа (9, 6, 5, 2)? 28.1-2

Пусть га - степень числа 2. Постройте сеть компараторов с га входами и га выходами глубины lg га, которая на находит наименьший и наибольший из входов (и выдаёт их на верхний и нижный провода соответственно).

28.1-3

Карлсон говорит Малышу, что в произвольном месте сортирующей сети можно добавить компаратор и сеть останется сортирующей. Покажите Малышу, что это не так, добавив компаратор в сеть рис. 28.2.

28.1-4

Докажите, что любая сортирующая сеть с га входами имеет глубину не меньше, чем lgra. 28.1-5

Докажите, что любая сортирующая сеть содержит не менее fi(ralgra) компараторов. 28.1-6

Покажите, что сеть на рисунке 28.3 является сортирующей, установив её родство с алгоритмом сортировки вставками (см. раздел 1.1).

28.1-7

Сеть компараторов с га входами и с компараторами представима в виде упорядоченного списка, содержащего с пар натуральных чисел от 1 до га. Паре соответствует компаратор, соединяющий г-ую и j-ую прямые. Список перечисляет компараторы слева направо. Используя это представление, придумайте (последовательный) алгоритм, который находит глубину сети за время О (га + с).

28.1-8 *

В сети некоторые элементы являются перевёрнутыми компараторами, выдающими на верхний выход максимальный из входов, а

на нижний - минимальный. Как преобразовать её в сеть только из обычных компараторов, эквивалентную исходной?

28.2. Правило нуля и единицы

Правило нуля и единицы (zero-one principle) говорит, что если сеть компараторов упорядочивает любую последовательность нулей и единиц, то является сортирующей (и упорядочивает любую последовательность чисел (целых, вещественных, или вообще элементов произвольного линейно упорядоченного множества). Тем самым, желая доказать, что построенная нами сеть является сортирующей, можно ограничиться рассмотрением входов из нулей и единиц - иногда это упрощает дело.

Доказательство использует понятие монотонно возрастающей функции (см. раздел 2.2).

Лемма 28.1 Если сеть компараторов преобразует последовательность а = (ai, а2,... , ап) в последовательность Ь = (b\, Ь2, , Ьп), а / - монотонно возрастающая функция, то подав на вход сети последовательность f(a) = (f(ai), /(аг), • • • , f(an)), мы получим на выходе f(b) = (/(6i), f(b2),...J(bn)).

Доказательство. Проверим это сначала для одного компаратора, то есть покажем, что компаратор, получив на вход /(ж) и /(у), выдаст на выходы /(тш(ж,у)) и /(тах(ж,у)) (рис. 28.4).

По определнию, на верхнем выходе будет тш(/(ж),/(у)), а на нижнем - тах(/(ж),/(у)). Остаётся заметить, что для возрастающей функции / из ж у следует /(ж) /(у), и поэтому

min(f (х), f (у)) = f(min(x,y)), max(f(x),f(y)) = f(max(x,y)).

Эта лемма показывает, что если применить ко входным значения компаратора хну монотонную функцию /, с его выходными значениями произойдёт то же самое.

Это свойство верно не только для одного компаратора, но и для любой сети компараторов. Пусть на входы сети поданы значения ai, а2,... ,ап. Через некоторое время на всех проводах (в том числе выходных) установятся некоторые значения. Теперь заменим входы на f(ai), f(a2),... , f(an). Что случится со значениями на проводах схемы? Как мы только что видели, выходы компараторов глубины 1 также заменятся на результат примерения к ним функции /. Следовательно, с выходами компараторов глубины 2 произойдёт то же самое, и так далее. Рассуждая по индукции, мы выдим,

Рис. 28.4 Компаратор и монотонная функция / (лемма 28.1)