101
правка
Изменения
Формулы для глубины и размера сети, переместил рис. 1 и 2
{{В разработке}}
<b>Сеть Бетчера <i>(Batcher odd-even mergesort)</i></b> {{---}} сортирующая сеть размером <tex>O(n \log^2n)</tex> и глубиной <tex>O(\log^2n)</tex>, где <tex>n</tex> {{---}} количество элементов для сортировки.
==Конструирование сетиБитоническая последовательность ==Для начала Сначала введем понятие битонической последовательности:все необходимые понятия для построения сортирующей сети Бетчера.
{{Определение
|definition=
<b>Битонической последовательностью</b> называется последовательность, которая сначала монотонно возрастает, а затем монотонно убывает, или последовательность, которая приводится к такому виду путем циклического сдвига.}}
{{Определение
|definition=
С первого взгляда битонические последовательности могут показаться бесполезными в деле построения сортирующих сетей, но на самом деле они обладают одним полезным свойством: если соединить вместе две отсортированные последовательности, причем одна из них должна быть отсортировала по возрастанию, а другая по убыванию {{---}} то получится битоническая последовательность. Далее этому свойству будет найдено применение.
Построим сеть, которая эффективно сортирует все битонические последовательности {{---}} т.н. <b>битонический сортировщик</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>
||[[Файл:Half-Cleaner1.png|250px200px|right|thumb|Рис.1 Полуфильтр для 8 проводов.]]
|}
{{Лемма|statement=
Если на вход в полуфильтр подать битоническую последовательность из нулей и единиц длиной <tex>n</tex>, то на выходе мы получим две битонические последовательности длиной <tex>\frac{n}{2}</tex> такие, что каждый элемент из верхней последовательности не превосходит любой элемент из нижней, и что одна из них будет <b>''однородной''</b> (clean) {{---}} целиком состоящей либо из нулей, либо из единиц.<br>
|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 случая разобраны на рис. 2. Для каждого из ни них лемма выполняется.
}}
Теперь используем полуфильтры для сортировки битонических последовательностей. Как только что было доказано, один полуфильтр разделяет битоническую последовательность на две равные части, одна из которых однородна, а другая сама по себе является битонической последовательностью, причем части расположены в правильном порядке. Тогда мы можем каждую часть снова отправить в полуфильтр вдвое меньшего размера, чем предыдущий. Затем, если нужно, четыре получившихся части снова отправить в полуфильтры и так далее, пока количество проводов в одной части больше <tex>1</tex>.
Схема битонического сортировщика для восьми входов приведен на рис. 3.
Так можно построить сеть для числа входов, являющегося степенью <tex>2</tex>двойки. Поскольку каждый вертикальный ряд полуфильтров вдвое сокращает число входов, которые необходимо отсортировать, глубина всей сети равна <tex>\log_{2}n</tex>, где <tex>n</tex> {{---}} число входов.Количество компараторов равно <tex dpi="150">\frac{n \log_2{n}}{2}</tex>, потому что размер одного полуфильтра на <tex>n</tex> входов {{---}} <tex>\frac{n}{2}</tex> компараторов, а в слое битонического сортировщика находится <tex>2^{i-1}</tex> полуфильтров, где <tex>i</tex> {{---}} номер слоя.||[[Файл:Half-Cleaner-proof.png|200px|right|thumb|Рис.2 Все случаи попадания битонической последовательности на полуфильтр.]]|}
Битонический сортировщик находит своё применение в конструкции так называемой <b>объединяющей сети</b>.
{{Определение
Объединяющая сеть является ничем иным как битоническим сортировщиком. Единственное отличие в том, что половина входных проводов расположена в обратном порядке (предполагается, что мы объединяем две сети одинакового размера <tex>\frac{n}{2}</tex>). Поэтому первый полуфильтр будет отличаться от остальных {{---}} он будет соединять <tex>i</tex>-ый провод не с <tex>\frac{n}{2} + i</tex>-ым, а с <tex>n-i+1</tex>-ым проводом. Схема объединяющей сети для восьми проводов приведена на рисунке 4.
Теперь, с помощью описанных выше объединяющих сетей мы построим параллельную версию [[сортировка слиянием|сортировки слиянием]]. <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>
||[[Файл:Sorter_8.png|365px|right|thumb|Рис.5 Сортирующая сеть для восьми проводов.]] <br>
|}
=== Точная глубина и размер сети ===
Оценим глубину этой сортирующей сети. Она состоит из <tex>\log_2{n}</tex> слоёв объединяющих сетей, которые имеют глубину, зависящую от слоя. В слое с номером <tex>i</tex> (<tex>1 \le i \le \log_2{n}</tex>) объединяющие сети имеют глубину <tex>\log_2{2^i}</tex>, потому как объединяют <tex>2^i</tex> проводов. Таким образом глубина всей сортирующей сети в точности равна <tex dpi = "150">\sum\limits^{\log_2{n}}_{i = 1}{\log_2{2^i}} = \sum\limits^{\log_2{n}}_{i = 1}{i} = \frac{1+\log_2{n}}{2} \log_2{n}</tex>.
Оценим размер сети. В объединяющей сети на <tex>n</tex> входов содержится <tex dpi="150">\frac{n \log_2{n}}{2}</tex> компараторов. Снова просуммируем формулу по числу объединяющих сетей и получим точную оценку <tex dpi = "150">\sum\limits^{\log_2{n}}_{i = 1}{ \frac{2^i \log_2{2^i}}{2} } = \sum\limits^{\log_2{n}}_{i = 1}{ 2^{i-1} i} = \frac{n \log_{2}^{2}{n} + 2 \log_2{n}}{4}</tex>.
==Источники==
