Сеть Бетчера

Эта статья находится в разработке!

Определение

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

Конструирование сети

Для начала введем понятие битонической последовательности:

Определение:

Битонической последовательностью называется последовательность, которая сначала монотонно возрастает, а затем монотонно убывает, или последовательность, которая приводится к такому виду путем циклического сдвига.

Сейчас мы будем рассматривать только нуль-единичные битонические последовательности:

Определение:

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

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

Сначала мы построим сеть, которая эффективно сортирует все битонические последовательности — т.н. битонический сортировщик.

Полуфильтр Основной элемент битонического сортировщика называется полуфильтром (half-cleaner). Каждый полуфильтр — сравнивающая сеть единичной глубины, в которой [math]i[/math]-й входной провод сравнивается со входным проводом с номером [math]\frac{n}{2} + i[/math], где [math]i=1,2,...,\frac{n}{2}[/math] (предположим, что [math]n[/math] — чётное). Рис.1 Полуфильтр для 8 проводов Лемма: Если на вход в полуфильтр подать битоническую последовательность из нулей и единиц длиной [math]n[/math], то на выходе мы получим две битонические последовательности длиной [math]\frac{n}{2}[/math] такие, что каждый элемент из верхней последовательности не превосходит любой элемент из нижней, и что одна из них будет однородной (clean) — целиком состоящей либо из нулей, либо из единиц. Доказательство: [math]\triangleright[/math] Для всех [math]i=1,2,...,\frac{n}{2}[/math] полуфильтр сравнивает провода с номерами [math]i[/math] и [math]i+\frac{n}{2}[/math]. Без потери общности будем рассматривать входную последовательность вида [math]0...01...10...0[/math] (для последовательности вида [math]1...10...01...1[/math] рассуждения аналогичны). В зависимости от того в каком блоке из последовательно расположенных нулей и единиц находится средняя точка [math]\frac{n}{2}[/math] входной последовательности, можно выделить 3 случая, причем один из случаев (когда средняя точка попадает на блок из единиц) можно разбить еще на 2 случая. Все 4 случая разобраны на рис. 2. Для каждого из ни лемма выполняется. [math]\triangleleft[/math]

Рис.2 Все случаи попадания битонической последовательности на полуфильтр

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

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

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

Битонический сортировщик находит своё применение в конструкции так называемой объединяющей сети. Определение: Объединяющая сеть (Merger) — сеть компараторов, объединяющая две отсортированные входные последовательности в одну отсортированную выходную последовательность. Построим объединяющую сеть на основе битонического сортировщика. Для этого рассмотрим наши отсортированные сходные последовательности: Отсортированная последовательность имеет вид [math]0^i1^j[/math] для целых [math]i, j\ge0[/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]i[/math]-ый провод не с [math]\frac{n}{2} + i[/math]-ым, а с [math]n-i+1[/math]-ым проводом. Пример объединяющей сети для 8 проводов приведен на рисунке 4.

Рис.4 Объединяющая сеть на 8 входов

Источники

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