101
правка
Изменения
м
<b>'''Сеть Бетчера <i>''(Batcher bitonic mergesort)</i></b> ''''' {{---}} сортирующая сеть размером <tex>O(n \log^2n)</tex> и глубиной <tex>O(\log^2n)</tex>, где <tex>n</tex> {{---}} количество элементов для сортировки. Её авторство принадлежит [http://en.wikipedia.org/wiki/Ken_Batcher Кену Бетчеру]. <br>
<b>'''Битонической последовательностью <i>''(bitonic sequence)</i></b> ''''' называется числовая последовательность, которая сначала монотонно возрастает, а затем монотонно убывает, или последовательность, которая приводится к такому виду путем циклического сдвига.}}
<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> идущих подряд единиц или нулей соответственно.}}
<b>'''Объединяющая сеть <i>''(Merger)</i></b> ''''' {{---}} сеть компараторов, объединяющая две отсортированные входные последовательности в одну отсортированную выходную последовательность.}}
Теги <b> и <i> заменены на вики-разметку
В этой статье будет описана сортирующая сеть для случая когда <tex>n</tex> {{---}} степень двойки (<tex>n = 2^k</tex>).
{{Определение
|definition=
Здесь мы воспользуемся [[0-1 принцип|0-1 принципом]] и будем рассматривать только нуль-единичные битонические последовательности:
{{Определение
|definition=
В качестве примеров нуль-единичной битонической последовательности можно привести последовательности <tex>00111000</tex>, <tex>11000111</tex>, <tex>1110</tex>, <tex>1</tex>, <tex>000</tex>. <br>
<!-- Эта фраза - собственного производства. Но раз АС считает её слишком "корменовской", то я её уберу -->
== Битонический сортировщик ==
Построим сеть, которая эффективно сортирует все битонические последовательности {{---}} т.н. <b>'''битонический сортировщик <i>''(bitonic sorter)</i></b>'''''. <br>
{|
|
=== Полуфильтр ===
Битонический сортировщик представляет собой каскад так называемых <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>
{{Определение
|definition=
Построим объединяющую сеть на основе битонического сортировщика. Для этого рассмотрим наши отсортированные входные последовательности: <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>, которую можно отсортировать в битоническом сортировщике с глубиной <tex>O(\log{n})</tex>.
