418
правок
Изменения
Новая страница: «== Нечетно-четная сортирующая сеть == {{Определение |definition= <b>Нечетно-четная сортирующая се...»
== Нечетно-четная сортирующая сеть ==
{{Определение
|definition=
<b>Нечетно-четная сортирующая сеть (odd-even sorting network)</b> на <tex>n</tex> входов <tex><a_1,a_2,...,a_n></tex> {{---}} это транспозиционная сортирующая сеть с <tex>n</tex> уровнями сравнивающих устройств, соединенных между собой по схеме "кирпичной кладки".
}}
Как видно, из рисунка, при <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<=j<=n</tex>.
{{Теорема
|statement=
Нечетно-четная сортирующая сеть действительно является сортирующей сетью.
|proof=
}}
== Перестановочная сеть ==
{{Определение
|definition=
<b>Перестановочная сортирующая сеть (permutation sorting network)</b> {{---}} сеть сортировки, содержащая на <tex>n</tex> входов и <tex>n</tex> выходов переключатели, позволяющие соединять входы сети с её выходами в соответствии с любой из <tex>n!</tex> возможных перестановок.
}}
== Периодическая сортировочная сеть ==
{{Определение
|definition=
<b>Нечетно-четная сортирующая сеть (odd-even sorting network)</b> на <tex>n</tex> входов <tex><a_1,a_2,...,a_n></tex> {{---}} это транспозиционная сортирующая сеть с <tex>n</tex> уровнями сравнивающих устройств, соединенных между собой по схеме "кирпичной кладки".
}}
Как видно, из рисунка, при <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<=j<=n</tex>.
{{Теорема
|statement=
Нечетно-четная сортирующая сеть действительно является сортирующей сетью.
|proof=
}}
== Перестановочная сеть ==
{{Определение
|definition=
<b>Перестановочная сортирующая сеть (permutation sorting network)</b> {{---}} сеть сортировки, содержащая на <tex>n</tex> входов и <tex>n</tex> выходов переключатели, позволяющие соединять входы сети с её выходами в соответствии с любой из <tex>n!</tex> возможных перестановок.
}}
== Периодическая сортировочная сеть ==
