Изменения

{{В разработке}}==Определение==<b>'''Сеть Бетчера <i>''' (англ. ''Batcher odd-even bitonic mergesort'')</i></b> {{---}} [[Сортирующие сети|сортирующая сеть ]] размером <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>). =Конструирование сети= Битоническая последовательность ==Для начала Сначала введем понятие битонической последовательности:все необходимые понятия для построения сортирующей сети Бетчера.

<b>'''Битонической последовательностью</b> ''' (англ. ''bitonic sequence'') называется последовательностьконечный упорядоченный набор (кортеж) из вещественных чисел, которая в котором они сначала монотонно возрастаетвозрастают, а затем монотонно убываетубывают, или последовательностьнабор, которая который приводится к такому виду путем циклического сдвига.}}Сейчас Здесь мы воспользуемся [[0-1 принцип|0-1 принципом]] и будем рассматривать только нуль-единичные битонические последовательности:

<b>'''Нуль-единичные битонические последовательности</b> ''' {{---}} последовательности кортежи из нулей и единиц вида <tex>0^i1^j0^k</tex> или <tex>1^i0^j1^k</tex> для целых <tex>i,j,k\ge0geqslant0</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>С первого взгляда битонические последовательности могут показаться бесполезными в деле построения сортирующих сетей, но на самом деле они обладают одним полезным свойством: если соединить вместе две отсортированные последовательности, причем одна из них должна быть отсортировала по возрастанию, а другая по убыванию {{---}} то получится битоническая последовательность. Далее этому свойству будет найдено применение.

===Битонический сортировщик===<!-- Эта фраза - собственного производства. Но раз АС считает её слишком "корменовской", то я её уберу -->Построим сеть<!-- С первого взгляда битонические последовательности могут показаться бесполезными в деле построения сортирующих сетей, которая эффективно сортирует все битонические но на самом деле они обладают одним полезным свойством: если соединить вместе две отсортированные последовательности , причем одна из них должна быть отсортировала по возрастанию, а другая по убыванию {{---}} тто получится битоническая последовательность.нДалее этому свойству будет найдено применение. <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> которая эффективно сортирует все битонические последовательности {{---}} чётноетак называемый '''битонический сортировщик''' (англ. ''bitonic sorter'').<br>||[[Файл:Half-Cleaner1.png‎|250px|right|thumb|Рис.1 Полуфильтр для 8 проводов.]]|}

Если на вход в полуфильтр подать битоническую последовательность из нулей и единиц длиной <tex>n</tex>, то на выходе мы получим две битонические последовательности длиной <tex>\fracdfrac{n}{2}</tex> такие, что каждый элемент из верхней последовательности не превосходит любой элемент из нижней, и что одна из них будет <b>'''однородной''</b> ' (англ. ''clean'') {{---}} целиком состоящей либо из нулей, либо из единиц.<br><!-- TODO: написать нормальное доказательство, а не копипасту из Кормена -->

Для всех <tex>i=1,2,...\dots,\fracdfrac{n}{2}</tex> полуфильтр сравнивает провода с номерами <tex>i</tex> и <tex>i+\fracdfrac{n}{2}</tex>. Без потери общности будем рассматривать входную последовательность вида <tex>0...01...10...0\dots01\dots10\dots0</tex> (для последовательности вида <tex>1...10...01...1\dots10\dots01\dots1</tex> рассуждения аналогичны). В зависимости от того в каком блоке из последовательно расположенных нулей и единиц находится средняя точка <tex>\fracdfrac{n}{2}</tex> входной последовательности, можно выделить 3 случая, причем один из случаев (когда средняя точка попадает на блок из единиц) можно разбить еще на 2 случая. Все 4 случая разобраны на рис. 2рисунке справа. Для каждого из ни них лемма выполняется.

||[[Файл:Half-Cleaner-proofCleaner1.png‎|200px262px|right|thumb|Рис.2 Все случаи попадания битонической последовательности на полуфильтрПолуфильтр для 8 проводов.]]

[[Файл:Half-Cleaner-proof.png‎|350px|center|thumb|Все случаи попадания битонической последовательности на полуфильтр.]] ==== Собственно битонический сортировщик =Построение битонического сортировщика ===

Так можно построить сеть для числа входов, являющегося степенью <tex>2</tex>[[Файл:Bitonic_sorter_8. Поскольку каждый вертикальный ряд полуфильтров вдвое сокращает число входов, которые необходимо отсортировать, глубина всей сети равна <tex>\log_{2}n</tex>, где <tex>n</tex> {{---}} число png|305px|center|thumb|Битонический сортировщик на восемь входовс выделенными полуфильтрами.]]

Так можно построить сеть для числа входов, являющегося степенью двойки. Поскольку каждый вертикальный ряд полуфильтров вдвое сокращает число входов, которые необходимо отсортировать, глубина всей сети равна <tex>\log_{2}n</tex>, где <tex>n</tex> {{---}} число входов.Количество компараторов равно <tex dpi="150">\frac{n \log_2{n}}{2}</tex>, потому что размер одного полуфильтра на <tex>n</tex> входов {{---}} <tex>\dfrac{n}{2}</tex> компараторов, а в слое битонического сортировщика находится <tex>2^{i-1}</tex> полуфильтров, где <tex>i</tex> {{---}} номер слоя, начиная с единицы. == Объединяющая сеть ===

<b>'''Объединяющая сеть <i>''' (Mergerангл. ''merger'')</i></b> {{---}} сеть компараторов, объединяющая две отсортированные входные последовательности в одну отсортированную выходную последовательность.}}Построим объединяющую сеть на основе битонического сортировщика. Для этого рассмотрим наши отсортированные входные последовательности: <br> Отсортированная последовательность имеет вид <tex>0^i1^j</tex> для целых <tex>i, j\ge0geqslant0</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>\dfrac{n}{2}</tex>). Поэтому первый полуфильтр будет отличаться от остальных {{---}} он будет соединять <tex>i</tex>-ый провод не с <tex>\dfrac{n}{2} + i</tex>-ым, а с <tex>n-i+1</tex>-ым проводом. Схема объединяющей сети для восьми проводов приведена ниже. Глубина и число компараторов в объединяющей сети очевидно те же, что и в битоническом сортировщике. [[Файл:Merger_8.png|294px|center|thumb|Сеть, объединяющая две отсортированные последовательности из четырёх чисел в одну отсортированную последовательность из восьми чисел.]] == Сортирующая сеть ===== Построение ===Теперь, с помощью описанных выше объединяющих сетей мы построим параллельную версию [[сортировка слиянием|сортировки слиянием]].  Пусть мы хотим отсортировать <tex>n=2^k</tex> входов, <tex>k</tex> {{---}} целое и <tex>k \geqslant0</tex>. Для этого сначала отсортируем пары проводов, поставив в первом слое компаратор между <tex>i</tex>-ым и <tex>i+1</tex>-ым проводом для нечетных <tex>i < n</tex>. Затем с помощью объединяющих сетей параллельно объединим отсортированные пары проводов в отсортированные четверки. Затем объединим отсортированные четверки в отсортированные восьмерки. И так далее, пока на выходе очередной объединяющей сети не будет <tex>n</tex> проводов. [[Файл:Sorter_8.png|549px|center|thumb|Сортирующая сеть для восьми проводов.]] Так мы построили сеть, сортирующую любую последовательность из нулей и единиц. А это означает, согласно [[0-1 принцип|0-1 принципу]], что она будет сортировать и любой набор чисел.

Объединяющая сеть является ничем иным как битоническим сортировщиком=== Точные формулы размера и глубины сети ===Оценим глубину этой сортирующей сети. Единственное отличие в том, что половина входных проводов расположена в обратном порядке (предполагается, что мы объединяем две сети одинакового размера Она состоит из <tex>\fraclog_2{n}{2}</tex>)слоёв объединяющих сетей и каждый слой имеет глубину, зависящую от его номера. Поэтому первый полуфильтр будет отличаться от остальных {{---}} он будет соединять В слое с номером <tex>i</tex>-ый провод не с (<tex>1 \leqslant i \leqslant \fraclog_2{n}</tex>) объединяющая сеть имеет глубину <tex>\log_2{2^i} + </tex>, потому как объединяет <tex>2^i</tex>-ым, а с проводов. Таким образом глубина всей сортирующей сети в точности равна <tex>\sum\limits^{\log_2{n}}_{i = 1}{\log_2{2^i}} = \sum\limits^{\log_2{n-}}_{i= 1}{i} = \dfrac{(1+1\log_2{n})\log_2{n}}{2}</tex>-ым проводом. Схема объединяющей сети для восьми проводов приведена на рисунке 4.

=== Сортирующая сеть ===Теперь, с помощью описанных выше объединяющих сетей мы построим параллельную версию [[сортировка слиянием|сортировки слиянием]]Оценим размер сети. <br>Пусть мы хотим отсортировать В объединяющей сети на <tex>n=2^k</tex> входов, содержится <tex>k</tex> \dfrac{n \log_2{---n}} целое и <tex>k \ge0{2}</tex>компараторов. Для этого сначала отсортируем пары проводов, поставив в первом слое компаратор между Снова просуммируем формулу по числу объединяющих сетей и получим точную оценку <tex>\sum\limits^{\log_2{n}}_{i = 1}{ \dfrac{2^i \log_2{2^i</tex>-ым и <tex>}}{2} } = \sum\limits^{\log_2{n}}_{i+= 1</tex>}{ 2^{i-ым проводом для нечетных <tex>1} i < } = \dfrac{n \log_{2}^{2}{n</tex>. Затем с помощью объединяющих сетей параллельно объединим отсортированные пары проводов в отсортированные четверки. Затем объединим отсортированные четверки в отсортированные восьмерки. И так далее, пока на выходе очередной объединяющей сети не будет <tex>} + 2 \log_2{n}}{4}</tex> проводов. <br>Схема такой сети приведена на рис. 5.

{|== См. также ==|* [[Файл:Bitonic_sorter_8.png|305px|left|thumb|Рис.3 Битонический сортировщик на восемь входов с выделенными полуфильтрами.Сортирующие сети для квадратичных сортировок]]||* [[Файл:Merger_8.png|294px|center|thumb|Рис.4 Сеть, объединяющая две отсортированные последовательности из четырёх чисел в одну отсортированную последовательность из восьми чисел.Сортировочные сети с особыми свойствами]]||[[Файл:Sorter_8.png|365px|right|thumb|Рис.5 Сортирующая сеть для восьми проводов.]] <br>|}==Примечания==

<references />==Источникиинформации==*[http[wikipedia://en.wikipedia.org/wiki/Batcher_odd-even_mergesort Bitonic_sorter | Wikipedia {{---}} Batcher odd-even mergesortBitonic sorter]]