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>В этой статье будет описана сортирующая сеть для случая когда <tex>n</tex> {{---}} степень двойки (<tex>n = 2^k</tex>).
== Битоническая последовательность ==
{{Определение
|definition=
<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> идущих подряд единиц или нулей соответственно.}}
В качестве примеров нуль-единичной битонической последовательности можно привести последовательности <tex>00111000</tex>, <tex>11000111</tex>, <tex>1110</tex>, <tex>1</tex>, <tex>000</tex>. <br>
<!-- Эта фраза - собственного производства. Но раз АС считает её слишком "корменовской", то я её уберу --><!-- С первого взгляда битонические последовательности могут показаться бесполезными в деле построения сортирующих сетей, но на самом деле они обладают одним полезным свойством: если соединить вместе две отсортированные последовательности, причем одна из них должна быть отсортировала по возрастанию, а другая по убыванию {{---}} то получится битоническая последовательность. Далее этому свойству будет найдено применение. -->Далее будет показано, что битоническую последовательность можно легко получить из двух отсортированных, поэтому если мы найдем способ эффективно её сортировать, то сможем столь же эффективно сливать (объединять) две отсортированные последовательности в одну. На этой операции и основывается принцип работы описываемой в этой статье сети сортировки.
== Битонический сортировщик ==
|
=== Полуфильтр ===
Каждый полуфильтр {{---}} сравнивающая сеть единичной глубины, в которой <tex>i</tex>-й входной провод сравнивается со входным проводом с номером <tex>\frac{n}{2} + i</tex>, где <tex>i=1,2,...,\frac{n}{2}</tex> (пусть количество входов <tex>n</tex> {{---}} чётное).<br>
||[[Файл:Half-Cleaner1.png|200px|right|thumb|Рис.1 Полуфильтр для 8 проводов.]]
|
{{Лемма|statement=
Если на вход в полуфильтр подать битоническую последовательность из нулей и единиц длиной <tex>n</tex>, то на выходе мы получим две битонические последовательности длиной <tex>\frac{n}{2}</tex> такие, что каждый элемент из верхней последовательности не превосходит любой элемент из нижней, и что одна из них будет <b>однородной ''однородной(clean)''</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>\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|200px350px|right|thumb|Рис.2 Все случаи попадания битонической последовательности на полуфильтр.]]
|}
|}
=== Точная глубина Точные формулы глубины и размер размера сети ===Оценим глубину этой сортирующей сети. Она состоит из <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>.
