Изменения
→Периодическая сортировочная сеть
{{Определение
|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=5</tex>]]
|}
{{Определение
|definition=
<b>Периодическая сортировочная сеть </b> (англ. ''periodic sorting network'')</b> на <tex>n</tex> входов <tex>\langlea_1langle 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 \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> компараторов, как и в сети битонного слияния.
{{Теорема
* [[Сортирующие сети для квадратичных сортировок]]
== Ссылки Источники информации ==
* Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 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]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортирующие сети]]
