Просмотр исходного текста страницы Сортировочные сети с особыми свойствами

== Нечетно-четная сортирующая сеть ==
{{Определение
|definition=
<b>Нечетно-четная сортирующая сеть</b> (англ. ''odd-even sorting network'') на <tex>n</tex> входов <tex>\langle a_1,a_2,...,a_n \rangle</tex> {{---}} это [[Примитивные_сортирующие_сети | транспозиционная сортирующая сеть]] с <tex>n</tex> уровнями сравнивающих устройств, соединенных между собой по схеме "кирпичной кладки".
}}
=== Примеры ===
{| cellpadding="0"
| [[Файл:odd-even_sorting_network(n=5).png|250px]] || [[Файл:odd-even_sorting_network(n=6v1).png|250px]] || [[Файл:odd-even_sorting_network(n=6v2).png|250px]]
|-
| Для <tex>n=5</tex> || Для <tex>n=6</tex> (Вариант 1) || Для <tex>n=6</tex> (Вариант 2)
|}
Как видно, из рисунка, при <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>.

Так же вполне очевидно, что если <tex>n</tex> четно, что имеется 2 варианта построения.

Одним из основных достоинств является то, что такую сортировку легко реализовать аппаратно, поскольку выполняются попеременно только 2 вида действий.
{{Теорема
|statement=
Нечетно-четная сортирующая сеть действительно является сортирующей сетью.
}}
Докажем теорему методом математической индукции по <tex>n</tex> линиям. Так же воспользуемся [[0-1_принцип | 0-1 принципом]].

'''База индукции.''' При <tex>n=1</tex> в сети не будет компараторов, но она очевидно будет являться сортирующей.
Допустим, что наше предположение верно и для случая, где сеть имеет <tex>n-1</tex> линий.
Рассмотрим случай с <tex>n</tex> линиями. Пусть на вход подается последовательность нулей и единиц: <tex>a=a_0,...,a_{n-1}</tex>.
Появляется 2 случая:

{| cellpadding="0"
| '''Случай 1.''' Если <tex>a_{n-1}=1</tex>, то компараторы <tex>[n-2:n-1]</tex> ничего не изменят. И компараторы на линиях <tex>\{0...n-1\}</tex> также не будут использовать <tex>a_{n-1}</tex> элемент. По нашему предположению, наша сеть отсортирует последовательность <tex>a_0,...,a_{n-2}</tex> длины <tex>n-1</tex>. Итак, элемент <tex>a_{n-1}</tex> уже находится на правильной позиции, следовательно мы получим отсортированную последовательность <tex>a</tex>. || [[Файл:odd-even__sorting_network_proof(1).png|thumb|300px]]
|-
| '''Случай 2.''' Если <tex>a_{n-1}=0</tex>, то этот элемент столкнувшись с любым компаратором будет совершать обмен (даже если обмен не является необходимым, когда другой элемент также <tex>0</tex>, результат будет таким же). Соответствующие компараторы могут быть замены путем скрещивания линий. По нашему предположению, наша сеть отсортирует последовательность <tex>a_0,...,a_{n-2}</tex> длины <tex>n-1</tex>.  Итак, элемент <tex>a_{n-1}</tex> путем прохождения сети будет помещен на правильную позиции, следовательно мы получим отсортированную последовательность <tex>a</tex>. || [[Файл:odd-even__sorting_network_proof(2).png|thumb|300px]]
|}

== Перестановочная сеть ==
{{Определение
|definition=
<b>Перестановочная сеть</b> (англ. ''permutation network'') {{---}} сеть сортировки, содержащая на <tex>n</tex> входов и <tex>n</tex> выходов переключатели, позволяющие соединять входы сети с её выходами в соответствии с любой из <tex>n!</tex> возможных перестановок.
}}
{{Определение
|definition=
<b>Перестановочная сортирующая сеть</b> (англ. ''permutation sorting network'') {{---}} сеть сортировки, содержащая последовательность компараторов <tex>[i_1:j_1]...[i_r:j_r]</tex>, где каждый модуль <tex>[i:j]</tex> может устанавливаться извне в одно из двух остояний: либо он передает свои входы без изменений, либо меняет местами <tex>x_i</tex> и <tex>x_j</tex> <tex>(</tex>независимо от значений <tex>x_i</tex> и <tex>x_j)</tex>.
}}
=== Примеры ===
{| cellpadding="0"
| [[Файл:permutation_network.png|thumb|300px|На рисунке показана рекурсивная схема перестановочной сети <tex>P_8</tex> на <tex>8</tex> входов и <tex>8</tex>, которая содержит две копии <tex>P_4</tex> и <tex>8</tex> переключателей <tex>(P_2)</tex>.]]
|}

== Периодическая сортировочная сеть ==
{{Определение
|definition=
<b>Периодическая сортировочная сеть</b> (англ. ''periodic sorting network'') на <tex>n</tex> входов <tex>\langle a_1,a_2,...,a_n \rangle</tex> {{---}} сеть сортировки, содержащая <tex>n = 2^t</tex> входов, где <tex>t</tex> {{---}} уровень сети, и у которой каждый уровень может быть построен с помощью рекурсивного алгоритма. 
}}

=== Примеры ===
[[Файл:periodic_sorting_network.png|thumb]]
Для начала раскрасим все линии красным или синим цветом в соответствии со следующими правилами:
Показанная на рисунке сеть следует считать иллюстрацией рекурсивного построения t-уровневой сети при <tex>n=2^t</tex> в случае <tex>t=4</tex>. Если пронумеровать линии входов от <tex>0</tex> до <tex>2^t-1</tex>, то <tex>l</tex>-й уровень имеет компараторы <tex>[i:j]</tex>, где <tex>i \bmod 2^{t+1-l} < 2^{t-l}</tex> и <tex>j=i \oplus (2^{t+1-l}-1)</tex>. Всего существует <tex>t\cdot2^{t-1}</tex> компараторов, как и в сети битонного слияния.

{{Теорема
|statement=
Если входные числа <tex>2^k</tex>-упорядочены при некотором <tex>k \geqslant 1</tex>, то периодическая сеть приведет к выходу, который будет <tex>2^{k-1}</tex> -упорядочен.

|proof=
[[Файл:periodic_sorting_network_proof.png|thumb]]

Если <tex>i \bmod 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>.

Такой способ так же годится и для случая <tex>k=2</tex>. Если вход <tex>4</tex>-упорядочен, красные линии содержат <tex>2^{t-1}</tex> чисел, которые являются <tex>2</tex>-упорядоченными; то же самое можно сказать относительно синих линий.
Очевидно, что результат является <tex>2</tex>-упорядоченным.

Теперь для <tex>k \geqslant 2</tex> можно предположить, что <tex>k \leqslant t</tex>. Первые <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> раз.

== См. также ==
* [[Примитивные сортирующие сети]]
* [[Сортирующие сети для квадратичных сортировок]]

== Источники информации ==
* Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 27.5, стр. 819
* Д.Э. Кнут. «Искусство программирования: Сортировка и поиск" Том 3, Глава 5.3.4, стр. 275
* [http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/networks/oetsen.htm Bachelor-Studiengang Angewandte Informatik {{---}} Odd-even transposition sort]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортирующие сети]]