Изменения
→Периодическая сортировочная сеть
{{Определение
|definition=
<b>Нечетно-четная сортирующая сеть </b> (англ. ''odd-even sorting network'')</b> на <tex>n</tex> входов <tex><\langle a_1,a_2,...,a_n>\rangle</tex> {{---}} это [[Примитивные_сортирующие_сети | транспозиционная сортирующая сеть]] с <tex>n</tex> уровнями сравнивающих устройств, соединенных между собой по схеме "кирпичной кладки".
}}
=== Примеры ===
{| 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'')</b> {{---}} сеть сортировки, содержащая на <tex>n</tex> входов и <tex>n</tex> выходов переключатели, позволяющие соединять входы сети с её выходами в соответствии с любой из <tex>n!</tex> возможных перестановок.
}}
{{Определение
|definition=
<b>Перестановочная сортирующая сеть </b> (англ. ''permutation sorting network'')</b> {{---}} сеть сортировки, содержащая последовательность компараторов <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>).]] || [[Файл:permutation_sorting_network.png|thumb|300px|Перестановочная сортирующая сеть для <tex>n=8</tex>]]
|}
{{Определение
|definition=
<b>Периодическая сортировочная сеть </b> (англ. ''periodic sorting network'')</b> на <tex>n</tex> входов <tex><\langle a_1,a_2,...,a_n>\rangle</tex> {{---}} сеть сортировки, содержащая <tex>n = 2^t</tex> входов</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 \mod bmod 2^{t+1-l} < 2^{t-l}</tex> и <tex>j=i 0x \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 \mod bmod 4 = </tex>
* <tex>0 \Rightarrow</tex> красный
* <tex>1 \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<=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]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортирующие сети]]
