42
правки
Изменения
Нет описания правки
{{В разработке}}
==Определение==
<b>Сеть Бетчера (Batcher odd-even mergesort)</b> - сортирующая сеть размером <tex>O(n log^2n)</tex> и глубиной <tex>O(log^2n)</tex>, где <tex>n</tex> - количество элементов для сортировки.
==Конструирование сети==
Для начала введем понятие битонической последовательности:
{{Определение
|definition=
Битонической последовательностью называется последовательность, которая сначала монотонно возрастает, а затем монотонно убывает, или последовательность, которая приводится к такому виду путем циклического сдвига.}}
В нашем случае мы будем рассматривать нуль-единичные битонические последовательности:
{{Определение
|definition=
Нуль-единичные битонические последовательности - последовательности вида <tex>0^i1^j0^k</tex> или <tex>1^i0^j1^k</tex> для <tex>i,j,k\le0</tex>}}
На первом этапе конструирования стоит задача построить сравнивающую сеть, которая будет сортировать любую нуль-единичную битоническую последовательность - битонический сортировщик.
[[Файл:Half-Cleaner1.png|300px|right|Half-Cleaner для 8 проводов]]
Битонический сортировщик состоит из нескольких каскадов, каждый из которых называется <b>''полуфильтром''</b> (half-cleaner). Каждый полуфильтр - сравнивающая сеть глубиной 1, в которой <tex>i</tex>-й входной провод сравнивается со входным проводом с номером <tex>i+\frac{n}{2}</tex>, где <tex>i=1,2,...,\frac{n}{2}</tex>.<br>
{{Лемма|statement=
Если на вход в полуфильтр подать битоническую последовательность из нулей и единиц длиной <tex>n</tex>, то на выходе мы получим две битонические последовательности длиной <tex>\frac{n}{2}</tex> такие, что каждый элемент из верхней последовательности не превосходит любой элемент из нижней, и что одна из них будет <b>''однородной''</b> (clean) - состоящей либо из нулей, либо из единиц.<br>
|proof=
}}
