418
правок
Изменения
Нет описания правки
<b>Нечетно-четная сортирующая сеть (odd-even sorting network)</b> на <tex>n</tex> входов <tex><a_1,a_2,...,a_n></tex> {{---}} это транспозиционная сортирующая сеть с <tex>n</tex> уровнями сравнивающих устройств, соединенных между собой по схеме "кирпичной кладки".
}}
=== Примеры ===Как видно, из рисунка, при <tex>i=1,2,...,n</tex> и <tex>d=1,2,...,n</tex> линия <tex>i</tex> соединена сравнивающим устройством на глубине <tex>d</tex> c линией <tex>j=i+(-1)^{i+d}</tex>, если <tex>1<=\leqslant j<=\leqslant n</tex>.
{{Теорема
|statement=
{{Определение
|definition=
<b>Перестановочная сортирующая сеть (permutation sorting network)</b> {{---}} сеть сортировки, содержащая на <tex>n</tex> входов и <tex>n</tex> выходов переключатели, позволяющие соединять входы сети с её выходами в соответствии с любой из <tex>n!</tex> возможных перестановок.
}}
=== Примеры ===
== Периодическая сортировочная сеть ==
{{Определение
|definition=
<b>Периодическая сортировочная сеть (periodic sorting network)</b> на <tex>n</tex> входов <tex><a_1,a_2,...,a_n></tex> {{---}} сеть сортировки, содержащая <tex>n = 2^t</tex> входов</tex>, где <tex>t</tex> - уровень сети, и у которой каждый уровень может быть построен с помощью рекурсивного алгоритма.
}}
=== Примеры ===
{{Теорема
|statement=
Если входные числа <tex>2^k</tex> - упорядочены при некотором <tex>k \geqslant 1</tex>, то периодическая сеть приведет к выходу, который будет <tex>2^{k-1}</tex> - упорядочен.
|proof=
Для начала раскрасим все линии красным или синим цветом в соответствии со следующими правилами:
Если <tex>i \mod 4 = </tex>
* <tex>0 \Rightarrow</tex> красный
* <tex>1 \Rightarrow</tex> синий
* <tex>2 \Rightarrow</tex> синий
* <tex>3 \Rightarrow</tex> красный
Теперь можно увидеть, что первые <tex>t-1</tex> уровней сети состоят из двух отдельных сетей: одна из <tex>2^{t-1}</tex> красных линий, а другая - из <tex>2^{t-1}</tex> синих линий. Компараторы на <tex>t</tex>-м уровне образуют сеть слияния, как в сетях битонного или четно-нечетного слияния. Таким образом, мы получили искомый результат при <tex>k=1</tex>.
Такой способ так же годится и для случая k=2. Если вход 4-упорядочен, красные линии содержат <tex>2^{t-1}</tex> чисел, которые являются 2-упорядоченными; то же самое можно сказать относительно синих линий.
Очевидно, что результат является 2-упорядоченным.
Теперь для <tex>k \geqslant 2</tex> можно предположить, что k<=t. Первые <tex>t-k+2</tex> уровней разделяются на <tex>2^{k-2}</tex> отдельных сетей размеров <tex>2^{t-k+2}</tex>, каждая из которых является <tex>2</tex>-упорядоченной в случае <tex>k=2</tex>; следовательно, линии являются <tex>2^{k-1}</tex>-упорядоченными после <tex>t-k+2</tex> уровней. Последующие уровни, очевидно, сохраняют <tex>2^{k-1}</tex>-упорядоченность, так как они обладают "вертикальной" периодичностью порядка <tex>2^{k-2}</tex>.
}}
Таким образом мы сможем сортировать <tex>2^t</tex> чисел, пропуская их через сеть <tex>t</tex> раз.
