Сортировочные сети с особыми свойствами — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «== Нечетно-четная сортирующая сеть == {{Определение |definition= <b>Нечетно-четная сортирующая се...»)
(нет различий)

Версия 10:35, 10 июня 2013

Нечетно-четная сортирующая сеть

Определение:
Нечетно-четная сортирующая сеть (odd-even sorting network) на [math]n[/math] входов [math]\lt a_1,a_2,...,a_n\gt [/math] — это транспозиционная сортирующая сеть с [math]n[/math] уровнями сравнивающих устройств, соединенных между собой по схеме "кирпичной кладки".

Как видно, из рисунка, при [math]i=1,2,...,n[/math] и [math]d=1,2,...,n[/math] линия [math]i[/math] соединена сравнивающим устройством на глубине [math]d[/math] c линией [math]j=i+(-1)^{i+d}[/math], если [math]1\lt =j\lt =n[/math].

Теорема:
Нечетно-четная сортирующая сеть действительно является сортирующей сетью.

Перестановочная сеть

Определение:
Перестановочная сортирующая сеть (permutation sorting network) — сеть сортировки, содержащая на [math]n[/math] входов и [math]n[/math] выходов переключатели, позволяющие соединять входы сети с её выходами в соответствии с любой из [math]n![/math] возможных перестановок.

Периодическая сортировочная сеть