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

Материал из Викиконспекты
Перейти к: навигация, поиск

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

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

Примеры

Odd-even sorting network(n=5).png Odd-even sorting network(n=6v1).png Odd-even sorting network(n=6v2).png
Для [math]n=5[/math] Для [math]n=6[/math] (Вариант 1) Для [math]n=6[/math] (Вариант 2)

Как видно, из рисунка, при [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 \leqslant j \leqslant n[/math].

Так же вполне очевидно, что если [math]n[/math] четно, что имеется 2 варианта построения.

Одним из основных достоинств является то, что такую сортировку легко реализовать аппаратно, поскольку выполняются попеременно только 2 вида действий.

Теорема:
Нечетно-четная сортирующая сеть действительно является сортирующей сетью.
Доказательство:
[math]\triangleright[/math]
Докажем теорему методом математической индукции по [math]n[/math] линиям.
[math]\triangleleft[/math]

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

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

Примеры

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

Определение:
Периодическая сортировочная сеть (periodic sorting network) на [math]n[/math] входов [math]\lt a_1,a_2,...,a_n\gt [/math] — сеть сортировки, содержащая [math]n = 2^t[/math] входов</tex>, где [math]t[/math] - уровень сети, и у которой каждый уровень может быть построен с помощью рекурсивного алгоритма.

Примеры

Periodic sorting network.png

Для начала раскрасим все линии красным или синим цветом в соответствии со следующими правилами: Показанная на рисунке сеть следует считать иллюстрацией рекурсивного построения t-уровневой сети при [math]n=2^t[/math] в случае [math]t=4[/math]. Если пронумеровать линии входов от [math]0[/math] до [math]2^t-1[/math], то [math]l[/math]-й уровень имеет компараторы [math][i:j][/math], где [math]i \mod 2^{t+1-l} \lt 2^{t-l}[/math] и [math]j=i 0x (2^{t+1-l}-1)[/math]. Всего существует [math]t\cdot2^{t-1}[/math] компараторов, как и в сети битонного слияния.

Теорема:
Если входные числа [math]2^k[/math] - упорядочены при некотором [math]k \geqslant 1[/math], то периодическая сеть приведет к выходу, который будет [math]2^{k-1}[/math] - упорядочен.
Доказательство:
[math]\triangleright[/math]
Periodic sorting network proof.png

Если [math]i \mod 4 = [/math]

  • [math]0 \Rightarrow[/math] красный
  • [math]1 \Rightarrow[/math] синий
  • [math]2 \Rightarrow[/math] синий
  • [math]3 \Rightarrow[/math] красный

Теперь можно увидеть, что первые [math]t-1[/math] уровней сети состоят из двух отдельных сетей: одна из [math]2^{t-1}[/math] красных линий, а другая - из [math]2^{t-1}[/math] синих линий. Компараторы на [math]t[/math]-м уровне образуют сеть слияния, как в сетях битонного или четно-нечетного слияния. Таким образом, мы получили искомый результат при [math]k=1[/math].

Такой способ так же годится и для случая k=2. Если вход 4-упорядочен, красные линии содержат [math]2^{t-1}[/math] чисел, которые являются 2-упорядоченными; то же самое можно сказать относительно синих линий. Очевидно, что результат является 2-упорядоченным.

Теперь для [math]k \geqslant 2[/math] можно предположить, что k<=t. Первые [math]t-k+2[/math] уровней разделяются на [math]2^{k-2}[/math] отдельных сетей размеров [math]2^{t-k+2}[/math], каждая из которых является [math]2[/math]-упорядоченной в случае [math]k=2[/math]; следовательно, линии являются [math]2^{k-1}[/math]-упорядоченными после [math]t-k+2[/math] уровней. Последующие уровни, очевидно, сохраняют [math]2^{k-1}[/math]-упорядоченность, так как они обладают "вертикальной" периодичностью порядка [math]2^{k-2}[/math].
[math]\triangleleft[/math]

Таким образом мы сможем сортировать [math]2^t[/math] чисел, пропуская их через сеть [math]t[/math] раз.

См. также

Ссылки

  • Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 27.5, стр. 819
  • Д.Э. Кнут. «Искусство программирования: Сортировка и поиск" Том 3, Глава 5.3.4, стр. 275
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Сортировочные_сети_с_особыми_свойствами&oldid=31558»