Сеть Бетчера — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 35 промежуточных версий 4 участников)
Строка 1: Строка 1:
{{В разработке}}
+
'''Сеть Бетчера''' (англ. ''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>.
<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 Кену Бетчеру].
+
 
 +
В этой статье будет описана сортирующая сеть для случая когда <tex>n</tex> {{---}} степень двойки (<tex>n = 2^k</tex>).
  
 
== Битоническая последовательность ==
 
== Битоническая последовательность ==
Строка 6: Строка 7:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
<b>Битонической последовательностью</b> называется последовательность, которая сначала монотонно возрастает, а затем монотонно убывает, или последовательность, которая приводится к такому виду путем циклического сдвига.}}
+
'''Битонической последовательностью''' (англ. ''bitonic sequence'') называется конечный упорядоченный набор (кортеж) из вещественных чисел, в котором они сначала монотонно возрастают, а затем монотонно убывают, или набор, который приводится к такому виду путем циклического сдвига.}}
Здесь мы будем рассматривать только нуль-единичные битонические последовательности:
+
Здесь мы воспользуемся [[0-1 принцип|0-1 принципом]] и будем рассматривать только нуль-единичные битонические последовательности:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
<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>0^i1^j0^k</tex> или <tex>1^i0^j1^k</tex> для целых <tex>i,j,k\geqslant0</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>00111000</tex>,  <tex>11000111</tex>,  <tex>1110</tex>,  <tex>1</tex>,  <tex>000</tex>.
С первого взгляда битонические последовательности могут показаться бесполезными в деле построения сортирующих сетей, но на самом деле они обладают одним полезным свойством: если соединить вместе две отсортированные последовательности, причем одна из них должна быть отсортировала по возрастанию, а другая по убыванию {{---}} то получится битоническая последовательность. Далее этому свойству будет найдено применение.
+
 
 +
<!-- Эта фраза - собственного производства. Но раз АС считает её слишком "корменовской", то я её уберу -->
 +
<!-- С первого взгляда битонические последовательности могут показаться бесполезными в деле построения сортирующих сетей, но на самом деле они обладают одним полезным свойством: если соединить вместе две отсортированные последовательности, причем одна из них должна быть отсортировала по возрастанию, а другая по убыванию {{---}} то получится битоническая последовательность. Далее этому свойству будет найдено применение. -->
 +
Далее будет показано, что битоническую последовательность можно легко получить из двух отсортированных, поэтому если мы найдем способ эффективно её сортировать, то сможем столь же эффективно сливать (объединять) две отсортированные последовательности в одну. На этой операции и основывается принцип работы описываемой в этой статье сети сортировки.
  
 
== Битонический сортировщик ==
 
== Битонический сортировщик ==
Построим сеть, которая эффективно сортирует все битонические последовательности {{---}} т.н. <b>битонический сортировщик</b>. <br>
+
Построим сеть, которая эффективно сортирует все битонические последовательности {{---}} так называемый '''битонический сортировщик''' (англ. ''bitonic sorter'').
  
 
{|
 
{|
 
|
 
|
 
=== Полуфильтр ===
 
=== Полуфильтр ===
Основной элемент битонического сортировщика называется <b>полуфильтром <i>(half-cleaner)</i></b>.
+
Битонический сортировщик представляет собой каскад так называемых '''полуфильтров''' (англ. ''half-cleaner'').
Каждый полуфильтр {{---}} сравнивающая сеть единичной глубины, в которой <tex>i</tex>-й входной провод сравнивается со входным проводом с номером <tex>\frac{n}{2} + i</tex>, где <tex>i=1,2,...,\frac{n}{2}</tex> (пусть количество входов <tex>n</tex> {{---}} чётное).<br>
+
Каждый полуфильтр {{---}} сеть компараторов единичной глубины, в которой <tex>i</tex>-й входной провод сравнивается со входным проводом с номером <tex>\dfrac{n}{2} + i</tex>, где <tex>i=1,2,\dots,\dfrac{n}{2}</tex> (число входов <tex>n</tex> {{---}} чётное).
||[[Файл:Half-Cleaner1.png‎|200px|right|thumb|Рис.1 Полуфильтр для 8 проводов.]]
+
 
|}
 
  
{|
 
|
 
 
{{Лемма|statement=
 
{{Лемма|statement=
Если на вход в полуфильтр подать битоническую последовательность из нулей и единиц длиной <tex>n</tex>, то на выходе мы получим две битонические последовательности длиной <tex>\frac{n}{2}</tex> такие, что каждый элемент из верхней последовательности не превосходит любой элемент из нижней, и что одна из них будет <b>''однородной''</b> (clean) {{---}} целиком состоящей либо из нулей, либо из единиц.<br>
+
Если на вход в полуфильтр подать битоническую последовательность из нулей и единиц длиной <tex>n</tex>, то на выходе мы получим две битонические последовательности длиной <tex>\dfrac{n}{2}</tex> такие, что каждый элемент из верхней последовательности не превосходит любой элемент из нижней, и что одна из них будет '''однородной''' (англ. ''clean'') {{---}} целиком состоящей либо из нулей, либо из единиц.
 
|proof=
 
|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>i=1,2,\dots,\dfrac{n}{2}</tex> полуфильтр сравнивает провода с номерами <tex>i</tex> и <tex>i+\dfrac{n}{2}</tex>. Без потери общности будем рассматривать входную последовательность вида <tex>0\dots01\dots10\dots0</tex> (для последовательности вида <tex>1\dots10\dots01\dots1</tex> рассуждения аналогичны). В зависимости от того в каком блоке из последовательно расположенных нулей и единиц находится средняя точка <tex>\dfrac{n}{2}</tex> входной последовательности, можно выделить 3 случая, причем один из случаев (когда средняя точка попадает на блок из единиц) можно разбить еще на 2 случая. Все 4 случая разобраны на рисунке справа. Для каждого из них лемма выполняется.
 
}}
 
}}
 +
||[[Файл:Half-Cleaner1.png‎|262px|right|thumb|Полуфильтр для 8 проводов.]]
 +
|}
 +
 +
[[Файл:Half-Cleaner-proof.png‎|350px|center|thumb|Все случаи попадания битонической последовательности на полуфильтр.]]
  
 
=== Построение битонического сортировщика ===
 
=== Построение битонического сортировщика ===
 
Теперь используем полуфильтры для сортировки битонических последовательностей. Как только что было доказано, один полуфильтр разделяет битоническую последовательность на две равные части, одна из которых однородна, а другая сама по себе является битонической последовательностью, причем части расположены в правильном порядке. Тогда мы можем каждую часть снова отправить в полуфильтр вдвое меньшего размера, чем предыдущий. Затем, если нужно, четыре получившихся части снова отправить в полуфильтры и так далее, пока количество проводов в одной части больше <tex>1</tex>.
 
Теперь используем полуфильтры для сортировки битонических последовательностей. Как только что было доказано, один полуфильтр разделяет битоническую последовательность на две равные части, одна из которых однородна, а другая сама по себе является битонической последовательностью, причем части расположены в правильном порядке. Тогда мы можем каждую часть снова отправить в полуфильтр вдвое меньшего размера, чем предыдущий. Затем, если нужно, четыре получившихся части снова отправить в полуфильтры и так далее, пока количество проводов в одной части больше <tex>1</tex>.
Схема битонического сортировщика для восьми входов приведен на рис. 3.
+
 
 +
[[Файл:Bitonic_sorter_8.png|305px|center|thumb|Битонический сортировщик на восемь входов с выделенными полуфильтрами.]]
  
 
Так можно построить сеть для числа входов, являющегося степенью двойки. Поскольку каждый вертикальный ряд полуфильтров вдвое сокращает число входов, которые необходимо отсортировать, глубина всей сети равна <tex>\log_{2}n</tex>, где <tex>n</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> {{---}} номер слоя.
+
Количество компараторов равно <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> {{---}} номер слоя, начиная с единицы.
||[[Файл:Half-Cleaner-proof.png‎|200px|right|thumb|Рис.2 Все случаи попадания битонической последовательности на полуфильтр.]]
 
|}
 
  
 
== Объединяющая сеть ==
 
== Объединяющая сеть ==
Строка 46: Строка 50:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
<b>Объединяющая сеть <i>(Merger)</i></b> {{---}} сеть компараторов, объединяющая две отсортированные входные последовательности в одну отсортированную выходную последовательность.}}
+
'''Объединяющая сеть''' (англ. ''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>.
 
  
Объединяющая сеть является ничем иным как битоническим сортировщиком. Единственное отличие в том, что половина входных проводов расположена в обратном порядке (предполагается, что мы объединяем две сети одинакового размера <tex>\frac{n}{2}</tex>). Поэтому первый полуфильтр будет отличаться от остальных {{---}} он будет соединять <tex>i</tex>-ый провод не с <tex>\frac{n}{2} + i</tex>-ым, а с <tex>n-i+1</tex>-ым проводом. Схема объединяющей сети для восьми проводов приведена на рисунке 4.
+
Отсортированная последовательность имеет вид <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>\dfrac{n}{2}</tex>). Поэтому первый полуфильтр будет отличаться от остальных {{---}} он будет соединять <tex>i</tex>-ый провод не с <tex>\dfrac{n}{2} + i</tex>-ым, а с <tex>n-i+1</tex>-ым проводом. Схема объединяющей сети для восьми проводов приведена ниже.
  
 
Глубина и число компараторов в объединяющей сети очевидно те же, что и в битоническом сортировщике.
 
Глубина и число компараторов в объединяющей сети очевидно те же, что и в битоническом сортировщике.
 +
 +
[[Файл:Merger_8.png|294px|center|thumb|Сеть, объединяющая две отсортированные последовательности из четырёх чисел в одну отсортированную последовательность из восьми чисел.]]
  
 
== Сортирующая сеть ==
 
== Сортирующая сеть ==
 
=== Построение ===
 
=== Построение ===
Теперь, с помощью описанных выше объединяющих сетей мы построим параллельную версию [[сортировка слиянием|сортировки слиянием]]. <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>
 
Схема такой сети приведена на рис. 5. Выше мы доказывали корректность элементов сортирующей сети только для векторов из нулей и единиц. Однако сама сеть будет сортировать любые числа согласно [[0-1 принцип|0-1 принципу]] (объединяющая сеть и битонический сортировщик тоже будут работать, но доказать это чуть сложнее).
 
  
{|
+
Пусть мы хотим отсортировать <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> проводов.
|[[Файл:Bitonic_sorter_8.png|305px|left|thumb|Рис.3 Битонический сортировщик на восемь входов с выделенными полуфильтрами.]]
+
 
||[[Файл:Merger_8.png|294px|center|thumb|Рис.4 Сеть, объединяющая две отсортированные последовательности из четырёх чисел в одну отсортированную последовательность из восьми чисел.]]
+
[[Файл:Sorter_8.png|549px|center|thumb|Сортирующая сеть для восьми проводов.]]
||[[Файл:Sorter_8.png|365px|right|thumb|Рис.5 Сортирующая сеть для восьми проводов.]] <br>
+
 
|}
+
Так мы построили сеть, сортирующую любую последовательность из нулей и единиц. А это означает, согласно [[0-1 принцип|0-1 принципу]], что она будет сортировать и любой набор чисел.
 +
 
 +
=== Точные формулы размера и глубины сети ===
 +
Оценим глубину этой сортирующей сети. Она состоит из <tex>\log_2{n}</tex> слоёв объединяющих сетей и каждый слой имеет глубину, зависящую от его номера. В слое с номером <tex>i</tex> (<tex>1 \leqslant i \leqslant \log_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+\log_2{n})\log_2{n}}{2}</tex>.
 +
 
 +
Оценим размер сети. В объединяющей сети на <tex>n</tex> входов содержится <tex>\dfrac{n \log_2{n}}{2}</tex> компараторов. Снова просуммируем формулу по числу объединяющих сетей и получим точную оценку <tex>\sum\limits^{\log_2{n}}_{i = 1}{ \dfrac{2^i \log_2{2^i}}{2} } = \sum\limits^{\log_2{n}}_{i = 1}{ 2^{i-1} i} = \dfrac{n \log_{2}^{2}{n} + 2 \log_2{n}}{4}</tex>.
  
=== Точная глубина и размер сети ===
+
== См. также ==
Оценим глубину этой сортирующей сети. Она состоит из <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>.
+
==Примечания==
  
==Источники==
+
<references />
*[http://en.wikipedia.org/wiki/Bitonic_sorter Wikipedia {{---}} Bitonic mergesort]
+
==Источники информации==
 +
*[[wikipedia:Bitonic_sorter | Wikipedia {{---}} Bitonic sorter]]
 
*Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2005. — С. 808—818.
 
*Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2005. — С. 808—818.
 
<!-- TODO: проверить 2007 издание Кормена и написать его -->
 
<!-- TODO: проверить 2007 издание Кормена и написать его -->
 +
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Сортирующие сети]]

Текущая версия на 19:33, 4 сентября 2022

Сеть Бетчера (англ. Batcher bitonic mergesort) — сортирующая сеть размером [math]O(n \log^2n)[/math] и глубиной [math]O(\log^2n)[/math], где [math]n[/math] — число элементов для сортировки. Её авторство принадлежит Кену Бетчеру[1].

В этой статье будет описана сортирующая сеть для случая когда [math]n[/math] — степень двойки ([math]n = 2^k[/math]).

Битоническая последовательность

Сначала введем все необходимые понятия для построения сортирующей сети Бетчера.

Определение:
Битонической последовательностью (англ. bitonic sequence) называется конечный упорядоченный набор (кортеж) из вещественных чисел, в котором они сначала монотонно возрастают, а затем монотонно убывают, или набор, который приводится к такому виду путем циклического сдвига.

Здесь мы воспользуемся 0-1 принципом и будем рассматривать только нуль-единичные битонические последовательности:

Определение:
Нуль-единичные битонические последовательности — кортежи из нулей и единиц вида [math]0^i1^j0^k[/math] или [math]1^i0^j1^k[/math] для целых [math]i,j,k\geqslant0[/math], где [math]1^i[/math] или [math]0^i[/math] обозначает [math]i[/math] идущих подряд единиц или нулей соответственно.

Приведем несколько примеров нуль-единичной битонической последовательности: [math]00111000[/math], [math]11000111[/math], [math]1110[/math], [math]1[/math], [math]000[/math].

Далее будет показано, что битоническую последовательность можно легко получить из двух отсортированных, поэтому если мы найдем способ эффективно её сортировать, то сможем столь же эффективно сливать (объединять) две отсортированные последовательности в одну. На этой операции и основывается принцип работы описываемой в этой статье сети сортировки.

Битонический сортировщик

Построим сеть, которая эффективно сортирует все битонические последовательности — так называемый битонический сортировщик (англ. bitonic sorter).

Полуфильтр

Битонический сортировщик представляет собой каскад так называемых полуфильтров (англ. half-cleaner). Каждый полуфильтр — сеть компараторов единичной глубины, в которой [math]i[/math]-й входной провод сравнивается со входным проводом с номером [math]\dfrac{n}{2} + i[/math], где [math]i=1,2,\dots,\dfrac{n}{2}[/math] (число входов [math]n[/math] — чётное).


Лемма:
Если на вход в полуфильтр подать битоническую последовательность из нулей и единиц длиной [math]n[/math], то на выходе мы получим две битонические последовательности длиной [math]\dfrac{n}{2}[/math] такие, что каждый элемент из верхней последовательности не превосходит любой элемент из нижней, и что одна из них будет однородной (англ. clean) — целиком состоящей либо из нулей, либо из единиц.
Доказательство:
[math]\triangleright[/math]
Для всех [math]i=1,2,\dots,\dfrac{n}{2}[/math] полуфильтр сравнивает провода с номерами [math]i[/math] и [math]i+\dfrac{n}{2}[/math]. Без потери общности будем рассматривать входную последовательность вида [math]0\dots01\dots10\dots0[/math] (для последовательности вида [math]1\dots10\dots01\dots1[/math] рассуждения аналогичны). В зависимости от того в каком блоке из последовательно расположенных нулей и единиц находится средняя точка [math]\dfrac{n}{2}[/math] входной последовательности, можно выделить 3 случая, причем один из случаев (когда средняя точка попадает на блок из единиц) можно разбить еще на 2 случая. Все 4 случая разобраны на рисунке справа. Для каждого из них лемма выполняется.
[math]\triangleleft[/math]
Полуфильтр для 8 проводов.
Все случаи попадания битонической последовательности на полуфильтр.

Построение битонического сортировщика

Теперь используем полуфильтры для сортировки битонических последовательностей. Как только что было доказано, один полуфильтр разделяет битоническую последовательность на две равные части, одна из которых однородна, а другая сама по себе является битонической последовательностью, причем части расположены в правильном порядке. Тогда мы можем каждую часть снова отправить в полуфильтр вдвое меньшего размера, чем предыдущий. Затем, если нужно, четыре получившихся части снова отправить в полуфильтры и так далее, пока количество проводов в одной части больше [math]1[/math].

Битонический сортировщик на восемь входов с выделенными полуфильтрами.

Так можно построить сеть для числа входов, являющегося степенью двойки. Поскольку каждый вертикальный ряд полуфильтров вдвое сокращает число входов, которые необходимо отсортировать, глубина всей сети равна [math]\log_{2}n[/math], где [math]n[/math] — число входов. Количество компараторов равно [math]\frac{n \log_2{n}}{2}[/math], потому что размер одного полуфильтра на [math]n[/math] входов — [math]\dfrac{n}{2}[/math] компараторов, а в слое битонического сортировщика находится [math]2^{i-1}[/math] полуфильтров, где [math]i[/math] — номер слоя, начиная с единицы.

Объединяющая сеть

Битонический сортировщик находит своё применение в конструкции так называемой объединяющей сети.

Определение:
Объединяющая сеть (англ. merger) — сеть компараторов, объединяющая две отсортированные входные последовательности в одну отсортированную выходную последовательность.

Построим объединяющую сеть на основе битонического сортировщика. Для этого рассмотрим наши отсортированные входные последовательности:

Отсортированная последовательность имеет вид [math]0^i1^j[/math] для целых [math]i, j\geqslant0[/math]. Запишем две входные последовательности как [math]0^i1^j[/math] и [math]0^k1^l[/math]. Если перевернуть вторую последовательность, получится отсортированная по невозрастанию последовательность [math]1^l0^k[/math]. Если теперь записать первую и перевернутую вторую последовательности подряд, получится битоническая последовательность [math]0^i1^{j+l}0^k[/math], которую можно отсортировать в битоническом сортировщике с глубиной [math]O(\log{n})[/math].

Объединяющая сеть является ничем иным как битоническим сортировщиком. Единственное отличие в том, что половина входных проводов расположена в обратном порядке (предполагается, что мы объединяем две сети одинакового размера [math]\dfrac{n}{2}[/math]). Поэтому первый полуфильтр будет отличаться от остальных — он будет соединять [math]i[/math]-ый провод не с [math]\dfrac{n}{2} + i[/math]-ым, а с [math]n-i+1[/math]-ым проводом. Схема объединяющей сети для восьми проводов приведена ниже.

Глубина и число компараторов в объединяющей сети очевидно те же, что и в битоническом сортировщике.

Сеть, объединяющая две отсортированные последовательности из четырёх чисел в одну отсортированную последовательность из восьми чисел.

Сортирующая сеть

Построение

Теперь, с помощью описанных выше объединяющих сетей мы построим параллельную версию сортировки слиянием.

Пусть мы хотим отсортировать [math]n=2^k[/math] входов, [math]k[/math] — целое и [math]k \geqslant0[/math]. Для этого сначала отсортируем пары проводов, поставив в первом слое компаратор между [math]i[/math]-ым и [math]i+1[/math]-ым проводом для нечетных [math]i \lt n[/math]. Затем с помощью объединяющих сетей параллельно объединим отсортированные пары проводов в отсортированные четверки. Затем объединим отсортированные четверки в отсортированные восьмерки. И так далее, пока на выходе очередной объединяющей сети не будет [math]n[/math] проводов.

Сортирующая сеть для восьми проводов.

Так мы построили сеть, сортирующую любую последовательность из нулей и единиц. А это означает, согласно 0-1 принципу, что она будет сортировать и любой набор чисел.

Точные формулы размера и глубины сети

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

Оценим размер сети. В объединяющей сети на [math]n[/math] входов содержится [math]\dfrac{n \log_2{n}}{2}[/math] компараторов. Снова просуммируем формулу по числу объединяющих сетей и получим точную оценку [math]\sum\limits^{\log_2{n}}_{i = 1}{ \dfrac{2^i \log_2{2^i}}{2} } = \sum\limits^{\log_2{n}}_{i = 1}{ 2^{i-1} i} = \dfrac{n \log_{2}^{2}{n} + 2 \log_2{n}}{4}[/math].

См. также

Примечания

Источники информации

  • Wikipedia — Bitonic sorter
  • Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2005. — С. 808—818.