101
правка
Изменения
Перенес картинки вниз
Основной элемент битонического сортировщика называется <b>полуфильтром <i>(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|centerright|thumb|Рис.1 Полуфильтр для 8 проводов.]]|}
{|
|
{{Лемма|statement=
Если на вход в полуфильтр подать битоническую последовательность из нулей и единиц длиной <tex>n</tex>, то на выходе мы получим две битонические последовательности длиной <tex>\frac{n}{2}</tex> такие, что каждый элемент из верхней последовательности не превосходит любой элемент из нижней, и что одна из них будет <b>''однородной''</b> (clean) {{---}} целиком состоящей либо из нулей, либо из единиц.<br>
||[[Файл:Half-Cleaner-proof.png|200px|right|thumb|Рис.2 Все случаи попадания битонической последовательности на полуфильтр.]]
|}
Теперь используем полуфильтры для сортировки битонических последовательностей. Как только что было доказано, один полуфильтр разделяет битоническую последовательность на две равные части, одна из которых однородна, а другая сама по себе является битонической последовательностью, причем части расположены в правильном порядке. Тогда мы можем каждую часть снова отправить в полуфильтр вдвое меньшего размера, чем предыдущий. Затем, если нужно, четыре получившихся части снова отправить в полуфильтры и так далее, пока количество проводов в одной части больше <tex>1</tex>.
Схема битонического сортировщика для восьми входов приведен на рис. 3.
Так можно построить сеть для числа входов, являющегося степенью <tex>2</tex>. Поскольку каждый вертикальный ряд полуфильтров вдвое сокращает число входов, которые необходимо отсортировать, глубина всей сети равна <tex>\log_{2}n</tex>, где <tex>n</tex> {{---}} число входов.
=== Объединяющая сеть ===
{{Определение
|definition=
Отсортированная последовательность имеет вид <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>, которую можно отсортировать в битоническом сортировщике с глубиной <tex>O(\log{n})</tex>.
Объединяющая сеть является ничем иным как битоническим сортировщиком. Единственное отличие в том, что половина входных проводов расположена в обратном порядке (предполагается, что мы объединяем две сети одинакового размера <tex>\frac{n}{2}</tex>). Поэтому первый полуфильтр будет отличаться от остальных {{---}} он будет соединять <tex>i</tex>-ый провод не с <tex>\frac{n}{2} + i</tex>-ым, а с <tex>n-i+1</tex>-ым проводом. Пример Схема объединяющей сети для 8 восьми проводов приведен приведена на рисунке 4.||[[Файл:Merger_8.png|294px|right|thumb|Рис.4 Сеть, объединяющая две отсортированные последовательности из 4 чисел в одну отсортированную последовательность из 8 чисел.]]|}
=== Сортирующая сеть ===
Теперь, с помощью описанных выше объединяющих сетей мы построим параллельную версию [[сортировка слиянием|сортировки слиянием]]. <br>
Пусть мы хотим отсортировать <tex>n=2^k</tex> входов, <tex>k</tex> {{---}} целое и <tex>k \ge0</tex>. Для этого сначала отсортируем пары проводов, поставив в первом слое компаратор между <tex>i</tex>-ым и <tex>i+1</tex>-ым проводом для нечетных <tex>i < n</tex>. Затем с помощью объединяющих сетей параллельно объединим отсортированные пары проводов в отсортированные четверки. Затем объединим отсортированные четверки в отсортированные восьмерки. И так далее, пока на выходе очередной объединяющей сети не будет <tex>n</tex> проводов. <br>
|}
==Источники==
*[http://en.wikipedia.org/wiki/Batcher_odd-even_mergesort Wikipedia {{---}} Batcher odd-even mergesort]
*Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2005. — С. 808—818.
<!-- TODO: проверить 2007 издание Кормена и написать его -->
