1302
правки
Изменения
м
Нет описания правки
'''Сеть Бетчера ''(Batcher bitonic mergesort)''''' {{---}} сортирующая сеть размером <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=
'''Нуль-единичные битонические последовательности''' {{---}} последовательности вида <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>
<!-- Эта фраза - собственного производства. Но раз АС считает её слишком "корменовской", то я её уберу -->
<!-- С первого взгляда битонические последовательности могут показаться бесполезными в деле построения сортирующих сетей, но на самом деле они обладают одним полезным свойством: если соединить вместе две отсортированные последовательности, причем одна из них должна быть отсортировала по возрастанию, а другая по убыванию {{---}} то получится битоническая последовательность. Далее этому свойству будет найдено применение. -->
=== Полуфильтр ===
Битонический сортировщик представляет собой каскад так называемых '''полуфильтров ''(half-cleaner)'''''.
Каждый полуфильтр {{---}} сеть компараторов единичной глубины, в которой <tex>i</tex>-й входной провод сравнивается со входным проводом с номером <tex>\frac{n}{2} + i</tex>, где <tex>i=1,2,...,\frac{n}{2}</tex> (количество входов <tex>n</tex> {{---}} чётное).<br>
{{Лемма|statement=
Если на вход в полуфильтр подать битоническую последовательность из нулей и единиц длиной <tex>n</tex>, то на выходе мы получим две битонические последовательности длиной <tex>\frac{n}{2}</tex> такие, что каждый элемент из верхней последовательности не превосходит любой элемент из нижней, и что одна из них будет <b>однородной ''(clean)''</b> {{---}} целиком состоящей либо из нулей, либо из единиц.<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 случая разобраны на рисунке справа. Для каждого из них лемма выполняется.
|definition=
'''Объединяющая сеть ''(Merger)''''' {{---}} сеть компараторов, объединяющая две отсортированные входные последовательности в одну отсортированную выходную последовательность.}}
Построим объединяющую сеть на основе битонического сортировщика. Для этого рассмотрим наши отсортированные входные последовательности: <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>.
== Сортирующая сеть ==
=== Построение ===
Теперь, с помощью описанных выше объединяющих сетей мы построим параллельную версию [[сортировка слиянием|сортировки слиянием]]. <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> проводов.
[[Файл:Sorter_8.png|549px|center|thumb|Сортирующая сеть для восьми проводов.]] <br>
Так мы построили сеть, сортирующую любую последовательность из нулей и единиц. А это означает, согласно [[0-1 принцип|0-1 принципу]], что она будет сортировать и любой набор чисел.
