133
правки
Изменения
→Битонический сортировщик
== Битонический сортировщик ==
Построим сеть, которая эффективно сортирует все битонические последовательности {{---}} так называемый '''битонический сортировщик '''(англ. ''bitonic sorter)''''').
{|
|
=== Полуфильтр ===
Битонический сортировщик представляет собой каскад так называемых '''полуфильтров '''(англ. ''half-cleaner)''''').
Каждый полуфильтр {{---}} сеть компараторов единичной глубины, в которой <tex>i</tex>-й входной провод сравнивается со входным проводом с номером <tex>\frac{n}{2} + i</tex>, где <tex>i=1,2,...,\frac{n}{2}</tex> (количество входов <tex>n</tex> {{---}} чётное).
