418
правок
Изменения
Нет описания правки
|statement=
Нечетно-четная сортирующая сеть действительно является сортирующей сетью.
Докажем теорему методом математической индукции по <tex>n</tex> линиям. Так же воспользуемся 0-1 принципом.
Рассмотрим случай с <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>. Итак, элемент a_{n-1} уже находится на правильной позиции, следовательно мы получим отсортированную последовательность <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>Периодическая сортировочная сеть (periodic sorting network)</b> на <tex>n</tex> входов <tex><a_1,a_2,...,a_n></tex> {{---}} сеть сортировки, содержащая <tex>n = 2^t</tex> входов</tex>, где <tex>t</tex> - уровень сети, и у которой каждый уровень может быть построен с помощью рекурсивного алгоритма.
=== Примеры ===
[[Файл:periodic_sorting_network.png|thumb]]
|statement=
Если входные числа <tex>2^k</tex> - упорядочены при некотором <tex>k \geqslant 1</tex>, то периодическая сеть приведет к выходу, который будет <tex>2^{k-1}</tex> - упорядочен.
|proof=
[[Файл:periodic_sorting_network_proof.png|thumb]]
