101
правка
Изменения
Нет описания правки
{{В разработке}}
<b>Сеть Бетчера <i>(Batcher odd-even 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=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 принципу]] (объединяющая сеть и битонический сортировщик тоже будут работать, но доказать это чуть сложнее).
{|
==Источники==
*[http://en.wikipedia.org/wiki/Batcher_odd-even_mergesort Bitonic_sorter Wikipedia {{---}} Batcher odd-even Bitonic mergesort]
*Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2005. — С. 808—818.
<!-- TODO: проверить 2007 издание Кормена и написать его -->
