Сортировочные сети с особыми свойствами

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

Определение:

Нечетно-четная сортирующая сеть (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] возможных перестановок.