101
правка
Изменения
Сортирующая сеть
{{В разработке}}
==Определение==
<b>Сеть Бетчера <i>(Batcher odd-even mergesort)</i></b> {{---}} сортирующая сеть размером <tex>O(n \log^2n)</tex> и глубиной <tex>O(\log^2n)</tex>, где <tex>n</tex> {{---}} количество элементов для сортировки.
==Конструирование сети==
<b>Нуль-единичные битонические последовательности</b> {{---}} последовательности вида <tex>0^i1^j0^k</tex> или <tex>1^i0^j1^k</tex> для целых <tex>i,j,k\ge0</tex>, где <tex>1^i</tex> или <tex>0^i</tex> обозначает <tex>i</tex> идущих подряд единиц или нулей соответственно.}}
В качестве примеров нуль-единичной битонической последовательности можно привести последовательности <tex>00111000</tex>, <tex>11000111</tex>, <tex>1110</tex>, <tex>1</tex>, <tex>000</tex>. <br>
С первого взгляда битонические последовательности могут показаться бесполезными в деле построения сортирующих сетей, но на самом деле они обладают одним полезным свойством: если соединить вместе две отсортированные последовательности, причем одна из них должна быть отсортировала по возрастанию, а другая по убыванию {{---}} то получится битоническая последовательность. Далее мы найдем этому свойству будет найдено применение.
===Битонический сортировщик===
{| <!-- Какие-то адовые костыли только чтобы разместить картинку справа от текста -->
|
====Полуфильтр====
Основной элемент битонического сортировщика называется <b>полуфильтром</bi> (half-cleaner)</i></b>.Каждый полуфильтр {{---}} сравнивающая сеть единичной глубины, в которой <tex>i</tex>-й входной провод сравнивается со входным проводом с номером <tex>\frac{n}{2} + i</tex>, где <tex>i=1,2,...,\frac{n}{2}</tex> (предположим, что пусть количество входов <tex>n</tex> {{---}} чётное).<br>[[Файл:Half-Cleaner1.png|250px|center|thumb|Рис.1 Полуфильтр для 8 проводов.]]
{{Лемма|statement=
Для всех <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 случая разобраны на рис. 2. Для каждого из ни лемма выполняется.
}}
||[[Файл:Half-Cleaner-proof.png|200px|right|thumb|Рис.2 Все случаи попадания битонической последовательности на полуфильтр.]]
|}
|
====Битонический сортировщик====
Теперь мы используем полуфильтры для сортировки битонических последовательностей. Как только что было доказано, один полуфильтр разделяет битоническую последовательность на две равные части, одна из которых однородна, а другая сама по себе является битонической последовательностью, причем части расположены в правильном порядке. Тогда мы можем каждую часть снова отправить в полуфильтр вдвое меньшего размера, чем предыдущий. Затем, если нужно, четыре получившихся части снова отправить в полуфильтры и так далее, пока количество проводов в частях одной части больше одного<tex>1</tex>.
Так можно построить сеть для числа входов, являющегося степенью <tex>2</tex>. Поскольку каждый вертикальный ряд полуфильтров вдвое сокращает число входов, которые необходимо отсортировать, глубина всей сети равна <tex>\log_{2}n</tex>, где <tex>n</tex> {{---}} число входов.
|definition=
<b>Объединяющая сеть <i>(Merger)</i></b> {{---}} сеть компараторов, объединяющая две отсортированные входные последовательности в одну отсортированную выходную последовательность.}}
Построим объединяющую сеть на основе битонического сортировщика. Для этого рассмотрим наши отсортированные сходные входные последовательности: <br>Отсортированная последовательность имеет вид <tex>0^i1^j</tex> для целых <tex>i, j\ge0</tex>. Запишем две входные последовательности как <tex>0^i1^j</tex> и <tex>0^k1^l</tex>. Если перевернуть вторую последовательность, получится отсортированная по невозрастанию последовательность <tex>1^l0^k</tex>. Если теперь записать их первую и перевернутую вторую последовательности подряд, получится битоническая последовательность <tex>0^i1^{j+l}0^k</tex>. <br>А битоническую последовательность , которую можно отсортировать в битоническом сортировщике с глубиной <tex>O(\log{n})</tex>.
|}
==Источники==
