133
правки
Изменения
→Полуфильтр
{{Лемма|statement=
Если на вход в полуфильтр подать битоническую последовательность из нулей и единиц длиной <tex>n</tex>, то на выходе мы получим две битонические последовательности длиной <tex>\frac{n}{2}</tex> такие, что каждый элемент из верхней последовательности не превосходит любой элемент из нижней, и что одна из них будет <b>'''однородной '''(англ. ''clean)''</b> ) {{---}} целиком состоящей либо из нулей, либо из единиц.
|proof=
Для всех <tex>i=1,2,...,\frac{n}{2}</tex> полуфильтр сравнивает провода с номерами <tex>i</tex> и <tex>i+\frac{n}{2}</tex>. Без потери общности будем рассматривать входную последовательность вида <tex>0...01...10...0</tex> (для последовательности вида <tex>1...10...01...1</tex> рассуждения аналогичны). В зависимости от того в каком блоке из последовательно расположенных нулей и единиц находится средняя точка <tex>\frac{n}{2}</tex> входной последовательности, можно выделить 3 случая, причем один из случаев (когда средняя точка попадает на блок из единиц) можно разбить еще на 2 случая. Все 4 случая разобраны на рисунке справа. Для каждого из них лемма выполняется.
[[Файл:Half-Cleaner-proof.png|350px|center|thumb|Все случаи попадания битонической последовательности на полуфильтр.]]
=== Построение битонического сортировщика ===
