Изменения

<b>Нечетно-четная сортирующая сеть </b> (англ. ''odd-even sorting network'')</b> на <tex>n</tex> входов <tex>\langle a_1,a_2,...,a_n \rangle</tex> {{---}} это [[Примитивные_сортирующие_сети | транспозиционная сортирующая сеть]] с <tex>n</tex> уровнями сравнивающих устройств, соединенных между собой по схеме "кирпичной кладки".

<b>Перестановочная сеть </b> (англ. ''permutation network'')</b> {{---}} сеть сортировки, содержащая на <tex>n</tex> входов и <tex>n</tex> выходов переключатели, позволяющие соединять входы сети с её выходами в соответствии с любой из <tex>n!</tex> возможных перестановок.

<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>.

| [[Файл: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=5</tex>]]

<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>t</tex> {{---}} уровень сети, и у которой каждый уровень может быть построен с помощью рекурсивного алгоритма.

Показанная на рисунке сеть следует считать иллюстрацией рекурсивного построения 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 \oplus (2^{t+1-l}-1)</tex>. Всего существует <tex>t\cdot2^{t-1}</tex> компараторов, как и в сети битонного слияния.

== Ссылки Источники информации ==

* [http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/networks/oetsen.htm Bachelor-Studiengang Angewandte Informatik {{---}} Odd-even transposition sort]