418
правок
Изменения
Нет описания правки
}}
=== Примеры ===
[[Файл:periodic_sorting_network.png|thumb]]
Для начала раскрасим все линии красным или синим цветом в соответствии со следующими правилами:
Показанная на рисунке сеть следует считать иллюстрацией рекурсивного построения t-уровневой сети при <tex>n=2^t</tex> в случае <tex>t=4</tex>. Если пронумеровать линии входов от <tex>0</tex> до <tex>2^t-1</tex>, то <tex>l</tex>-й уровень имеет компараторы <tex>[i:j]</tex>, где <tex>i \mod 2^{t+1-l} < 2^{t-l}</tex> и <tex>j=i 0x (2^{t+1-l}-1)</tex>. Всего существует <tex>t\cdot2^{t-1}</tex> компараторов, как и в сети битонного слияния.
{{Теорема
|statement=
Если входные числа <tex>2^k</tex> - упорядочены при некотором <tex>k \geqslant 1</tex>, то периодическая сеть приведет к выходу, который будет <tex>2^{k-1}</tex> - упорядочен.
|proof=
Если <tex>i \mod 4 = </tex>
}}
Таким образом мы сможем сортировать <tex>2^t</tex> чисел, пропуская их через сеть <tex>t</tex> раз.
== См. также ==
* [[Примитивные сортирующие сети]]
* [[Сортирующие сети для квадратичных сортировок]]
== Ссылки ==
* Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 27.5, стр. 819
* Д.Э. Кнут. «Искусство программирования: Сортировка и поиск" Том 3, Глава 5.3.4, стр. 275
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортирующие сети]]
