Ki -4-Ki -1-Кз -3-Ka -2-

-2 - K -З-Кз -A-К,

Рис. 44. Еще один способ представления сортировки последовательности (4,1, 3, 2) посредством сети, изображенной на рис. 43.

начнут в момент t + Z выводиться снизу в рассортированном порядке, если включить соответствующий элемент задержки на линиях К[ и К.

При разработке теории сетей сортировки удобно изображать их несколько иным способом. На рис. 44 числа поступают слева, а модули компараторов представлены в виде вертикальных соединений между двумя прямыми; каждый компаратор вызывает, если необходима, перестановку своих входов таким образом, что после прохождения компаратора большее число оказывается на нижней, линии. В правой части диаграммы все числа упорядочены сверху вниз.

Ранее, изучая методы оптимальной сортировки, мы уделяли основное внимание минимизации числа сравнений, почти (или совсем) не учитывая перемещение данных либо сложность структуры принятия решений, которые связаны с таким методом сортировки. В этом отношении сети сортировки имеют некоторое преимущество, так как данные могут храниться в п ячейках, а структура принятия решений "прямолинейна"; нет необходимости запоминать результаты предыдущих сравнений - план неизменен и фиксирован заранее. Еще одним важным преимуществом сетей сортировки является то, что часть операций можно совмещать, т. е. выполнять их параллельно (если в нашем распоряжении имеется компьютер с соответствующей архитектурой). Например, пять шагов на рис. 43 и 44 сокращаются до трех, если организовать одновременные неперекрывающиеся операции сравнения, так как можно объединить первые два и следующие два шага. Ниже в данном разделе мы используем это свойство сетей сортировки. Таким образом, сети сортировки могут оказаться очень полезными на практике, хотя возможность построения эффективной сети сортировки п элементов при больших п вовсе не очевидна; возможно, мы обнаружим, что для поддержания однородной структуры решений требуется много дополнительных сравнений.

Хп-1

Хп Хп+1

•п+1

(а) (Ь)

Рис. 45. Получение (п + 1)-элементных сортировщиков из п-элементных: (а) вставка, (Ь) выбор.

Если дана сеть для п элементов, имеется два простых способа построения сети сортировки для п + I элементов: один - с использованием принципа вставки, а другой - принципа выбора. На рис. 45, (а) показано, как (п + 1)-й элемент может быть вставлен на нужное место после того, как первые п элементов рассортированы, а на рис. 45, (Ь) показано, как можно выбрать наибольший элемент, прежде чем перейти к сортировке остальных элементов. Многократное применение процедуры, показанной на рис. 45, (а), позволяет получить сетевой аналог метода простых вставок (алгоритм 5.2.IS), а многократное применение процедуры на рис. 45, (Ь) приводит к сетевому аналогу метода пузырька (алгоритм 5.2.2В).

Il/ / . ,

(а) (b)

Рис. 46. Сетевые аналоги элементарных схем внутренней сортировки, которые получены в результате многократного применения операции, представленной на рис. 45: (а) простая вставка, (Ь) метод пузырька.

На рис. 46 изображены соответствующие сети для шести элементов. Интересно заметить, что если сжать каждую сеть, чтобы обеспечить выполнение одновременных операций, то оба метода сведутся к одной и той же "треугольной" процедуре с (2п - 3) стадиями (рис. 47).

Рис. 47. При параллельном выполнении операций метод простой вставки совпадает с методом пузырька!.

Легко доказать, что сети, представленные на рис. 43 и 44, позволяют сортировать любое множество из четырех чисел, поскольку первые четыре компаратора направляют наименьший и наибольший элементы на положенные им места, а последний компаратор располагает в требуемом порядке остальные два элемента. Однако не всегда так легко сказать, будет ли данная сеть сортировать все возможные входные последовательности; например, сети

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

Теорема Z (Принцип нулей и единиц). Если сеть с п входами сортирует в порядке неубывания все 2" последовательностей из О и 1, то она будет сортировать в том же порядке любую последовательность п чисел.

Доказательство. (Это частный случай теоремы Бурисиуса (Bouricius); см. упр. 5.3.1-12.) Если f{x) - любая монотонная функция, для которой f{x) < f{y) при X < у, и если данная сеть преобразует (xi,...,Хп) в (j/i,..., j/„), то, как нетрудно видеть, эта сеть преобразует (/(ц),...,/(а;„)) в (/(j/i),...,/(г/„)). Если yi > yi+i при некотором г, то рассмотрим монотонную функцию /, которая для всех чисел < yi принимает значение О, а для всех чисел > j/i - значение 1. Эта функция определяет последовательность нулей иединиц (/(ij),...,/(а;„)), которая не сортируется данной сетью. Значит, если все последовательности 0-1 поддаются сортировке, то будем иметь yi < yi+i для всех 1 < г < п.

Принцип нулей и единиц довольно полезен для построения сетей сортировки. В качестве нетривиального примера можно с его помощью вывести обобщенный вариант "обменной сортировки со слиянием" Бэтчера (алгоритм 5.2.2М). Идея состоит в том, чтобы сортировать m-f-n элементов, сортируя первые тп и последние п элементов независимо, а затем "пропустить" результат через {т,п)-сеть слияния. Построить (т,п)-сеть слияния можно по индукции следующим образом.

a) Если т. - О или п = О, то сеть пуста. Если m = п = 1, то сеть состоит из единственного модуля компаратора.

b) Если тп > 1, обозначим сливаемые последовательности через {xi,... ,Хт) и {У1,---,Уп}- Сольем "нечетные последовательности" {х1,хз,... ,x2im/2\-i) и {у1,Уз, •••,2/2Гп/21-1) и получим рассортированный результат {vi,V2,... ,vim/2-\ + \n/2]); сольем "четные последовательности" {х2,Х4,..., Х2[т/2\) и {у2,У4, - , 2/2[п/2J) и получим рассортированный результат («ьгуг,.. •, W[m/2j + [n/2j)- И наконец, применим операции сравнения-обмена

Wi:V2, W2:V3, Юз:У4, Wlm/2\ + [n/2\ -v (1)

к последовательности

{vi,Wi,V2,W2,V3,W3,..., Vym/2l + ln/2\ , Wlm/2\ + [n/2\ , v, v") (2)

Теперь результат будет рассортирован. (!) Здесь v* = vym/2\ + [n/2\+i не существует, если тип оба четные, и v** = vym/2\ + in/2\+2 существует, лишь если тип оба нечетные; общее число модулей компараторов, указанных в (1), равно [(m-f-n-1)/2J.

Назовем (т,п)-сеть слияния Бэтчера четно-нечетным слиянием. Построенное в соответствии с этими принципами (4,7)-слияние показано на рис. 48.

Чтобы доказать, что эта довольно странная процедура действительно работает при тп > 1, воспользуемся принципом нулей и единиц и проверим ее на всех последовательностях О и 1. После начальных сортировок тип последовательность {xi,... ,Хт) будет состоять из к нулей, за которыми следуют т - к единиц, а последовательность (j/i,...,Ут) - из / нулей с последующими п - / единицами при некоторых к и I. Значит, последовательность {vi,V2,...) будет состоять из точно \к/2] -f- [ 2] нулей с последующими единицами, а {wi,W2----) - из [к/2} -f- [1/2}