1632
правки
Изменения
м
rollbackEdits.php mass rollback
'''Сеть Бетчера''' (англ. ''Batcher bitonic mergesort'') {{---}} [[Сортирующие сети|сортирующая сеть]] размером <tex>O(n \log^2n)</tex> и глубиной <tex>O(\log^2n)</tex>, где <tex>n</tex> {{---}} количество число элементов для сортировки. Её авторство принадлежит Кену Бетчеру<ref>[http://en.wikipedia.org/wiki/Ken_Batcher Wikipedia {{---}} Ken Batcher]</ref>.
В этой статье будет описана сортирующая сеть для случая когда <tex>n</tex> {{---}} степень двойки (<tex>n = 2^k</tex>).
=== Полуфильтр ===
Битонический сортировщик представляет собой каскад так называемых '''полуфильтров''' (англ. ''half-cleaner'').
Каждый полуфильтр {{---}} сеть компараторов единичной глубины, в которой <tex>i</tex>-й входной провод сравнивается со входным проводом с номером <tex>\fracdfrac{n}{2} + i</tex>, где <tex>i=1,2,\dots,\fracdfrac{n}{2}</tex> (количество число входов <tex>n</tex> {{---}} чётное).
{{Лемма|statement=
Если на вход в полуфильтр подать битоническую последовательность из нулей и единиц длиной <tex>n</tex>, то на выходе мы получим две битонические последовательности длиной <tex>\fracdfrac{n}{2}</tex> такие, что каждый элемент из верхней последовательности не превосходит любой элемент из нижней, и что одна из них будет '''однородной''' (англ. ''clean'') {{---}} целиком состоящей либо из нулей, либо из единиц.
|proof=
Для всех <tex>i=1,2,\dots,\fracdfrac{n}{2}</tex> полуфильтр сравнивает провода с номерами <tex>i</tex> и <tex>i+\fracdfrac{n}{2}</tex>. Без потери общности будем рассматривать входную последовательность вида <tex>0\dots01\dots10\dots0</tex> (для последовательности вида <tex>1\dots10\dots01\dots1</tex> рассуждения аналогичны). В зависимости от того в каком блоке из последовательно расположенных нулей и единиц находится средняя точка <tex>\fracdfrac{n}{2}</tex> входной последовательности, можно выделить 3 случая, причем один из случаев (когда средняя точка попадает на блок из единиц) можно разбить еще на 2 случая. Все 4 случая разобраны на рисунке справа. Для каждого из них лемма выполняется.
}}
||[[Файл:Half-Cleaner1.png|262px|right|thumb|Полуфильтр для 8 проводов.]]
Так можно построить сеть для числа входов, являющегося степенью двойки. Поскольку каждый вертикальный ряд полуфильтров вдвое сокращает число входов, которые необходимо отсортировать, глубина всей сети равна <tex>\log_{2}n</tex>, где <tex>n</tex> {{---}} число входов.
Количество компараторов равно <tex dpi="150">\frac{n \log_2{n}}{2}</tex>, потому что размер одного полуфильтра на <tex>n</tex> входов {{---}} <tex>\fracdfrac{n}{2}</tex> компараторов, а в слое битонического сортировщика находится <tex>2^{i-1}</tex> полуфильтров, где <tex>i</tex> {{---}} номер слоя, начиная с единицы.
== Объединяющая сеть ==
Отсортированная последовательность имеет вид <tex>0^i1^j</tex> для целых <tex>i, j\geqslant0</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>\fracdfrac{n}{2}</tex>). Поэтому первый полуфильтр будет отличаться от остальных {{---}} он будет соединять <tex>i</tex>-ый провод не с <tex>\fracdfrac{n}{2} + i</tex>-ым, а с <tex>n-i+1</tex>-ым проводом. Схема объединяющей сети для восьми проводов приведена ниже.
Глубина и число компараторов в объединяющей сети очевидно те же, что и в битоническом сортировщике.
=== Точные формулы размера и глубины сети ===
Оценим глубину этой сортирующей сети. Она состоит из <tex>\log_2{n}</tex> слоёв объединяющих сетей и каждый слой имеет глубину, зависящую от его номера. В слое с номером <tex>i</tex> (<tex>1 \le leqslant i \le leqslant \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} = \fracdfrac{(1+\log_2{n})\log_2{n}}{2}</tex>.
Оценим размер сети. В объединяющей сети на <tex>n</tex> входов содержится <tex dpi="150">\fracdfrac{n \log_2{n}}{2}</tex> компараторов. Снова просуммируем формулу по числу объединяющих сетей и получим точную оценку <tex dpi = "150">\sum\limits^{\log_2{n}}_{i = 1}{ \fracdfrac{2^i \log_2{2^i}}{2} } = \sum\limits^{\log_2{n}}_{i = 1}{ 2^{i-1} i} = \fracdfrac{n \log_{2}^{2}{n} + 2 \log_2{n}}{4}</tex>.
== См.также ==
* [[Сортирующие сети для квадратичных сортировок]]
* [[Сортировочные сети с особыми свойствами]]
==Примечания==
<references />
==Источники информации==
*[http[wikipedia://en.wikipedia.org/wiki/Bitonic_sorter | Wikipedia {{---}} Bitonic mergesortsorter]]
*Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2005. — С. 808—818.
<!-- TODO: проверить 2007 издание Кормена и написать его -->
