Сеть Бетчера — различия между версиями
Murtaught (обсуждение | вклад) (Начаты работы по разгребанию завалов) |
Murtaught (обсуждение | вклад) (Объединяющая сеть) |
||
Строка 38: | Строка 38: | ||
====Битонический сортировщик==== | ====Битонический сортировщик==== | ||
Теперь мы используем полуфильтры для сортировки битонических последовательностей. Как только что было доказано, один полуфильтр разделяет битоническую последовательность на две равные части, одна из которых однородна, а другая сама по себе является битонической последовательностью, причем части расположены в правильном порядке. Тогда мы можем каждую часть снова отправить в полуфильтр вдвое меньшего размера, чем предыдущий. Затем, если нужно, четыре получившихся части снова отправить в полуфильтры и так далее, пока количество проводов в частях больше одного. | Теперь мы используем полуфильтры для сортировки битонических последовательностей. Как только что было доказано, один полуфильтр разделяет битоническую последовательность на две равные части, одна из которых однородна, а другая сама по себе является битонической последовательностью, причем части расположены в правильном порядке. Тогда мы можем каждую часть снова отправить в полуфильтр вдвое меньшего размера, чем предыдущий. Затем, если нужно, четыре получившихся части снова отправить в полуфильтры и так далее, пока количество проводов в частях больше одного. | ||
+ | |||
+ | Так можно построить сеть для числа входов, являющегося степенью <tex>2</tex>. Поскольку каждый вертикальный ряд полуфильтров вдвое сокращает число входов, которые необходимо отсортировать, глубина всей сети равна <tex>\log_{2}n</tex>, где <tex>n</tex> {{---}} число входов. | ||
||[[Файл:Bitonic_sorter_8.png|305px|right|thumb|Рис.3 Битонический сортировщик на 8 входов с выделенными полуфильтрами.]] | ||[[Файл:Bitonic_sorter_8.png|305px|right|thumb|Рис.3 Битонический сортировщик на 8 входов с выделенными полуфильтрами.]] | ||
|} | |} | ||
+ | === Объединяющая сеть === | ||
+ | {| | ||
+ | |Битонический сортировщик находит своё применение в конструкции так называемой <b>объединяющей сети</b>. | ||
+ | {{Определение | ||
+ | |definition= | ||
+ | <b>Объединяющая сеть <i>(Merger)</i></b> {{---}} сеть компараторов, объединяющая две отсортированные входные последовательности в одну отсортированную выходную последовательность.}} | ||
+ | Построим объединяющую сеть на основе битонического сортировщика. Для этого рассмотрим наши отсортированные сходные последовательности: <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>. <br> | ||
+ | А битоническую последовательность можно отсортировать в битоническом сортировщике с глубиной <tex>O(\log{n})</tex>. | ||
+ | |||
+ | Итак, объединяющая сеть является ничем иным как битоническим сортировщиком. Единственное отличие в том, что половина входных проводов расположена в обратном порядке (предполагается, что мы объединяем две сети одного размера в одну). Поэтому первый полуфильтр будет отличаться от остальных {{---}} он будет соединять <tex>i</tex>-ый провод не с <tex>\frac{n}{2} + i</tex>-ым, а с <tex>n-i+1</tex>-ым проводом. Пример объединяющей сети для 8 проводов приведен на рисунке 4. | ||
+ | ||[[Файл:Merger_8.png|294px|right|thumb|Рис.4 Объединяющая сеть на 8 входов]] | ||
+ | |} | ||
==Источники== | ==Источники== | ||
*[http://en.wikipedia.org/wiki/Batcher_odd-even_mergesort Wikipedia {{---}} Batcher odd-even mergesort] | *[http://en.wikipedia.org/wiki/Batcher_odd-even_mergesort Wikipedia {{---}} Batcher odd-even mergesort] | ||
*Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2005. — С. 808—818. | *Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2005. — С. 808—818. | ||
<!-- TODO: проверить 2007 издание Кормена и написать его --> | <!-- TODO: проверить 2007 издание Кормена и написать его --> |
Версия 03:07, 5 июня 2012
Содержание
Определение
Сеть Бетчера (Batcher odd-even mergesort) — сортирующая сеть размером
и глубиной , где — количество элементов для сортировки.Конструирование сети
Для начала введем понятие битонической последовательности:
Определение: |
Битонической последовательностью называется последовательность, которая сначала монотонно возрастает, а затем монотонно убывает, или последовательность, которая приводится к такому виду путем циклического сдвига. |
Сейчас мы будем рассматривать только нуль-единичные битонические последовательности:
Определение: |
Нуль-единичные битонические последовательности — последовательности вида | или для целых , где или обозначает идущих подряд единиц или нулей соответственно.
В качестве примеров нуль-единичной битонической последовательности можно привести последовательности
С первого взгляда битонические последовательности могут показаться бесполезными в деле построения сортирующих сетей, но на самом деле они обладают одним полезным свойством: если соединить вместе две отсортированные последовательности, причем одна из них должна быть отсортировала по возрастанию, а другая по убыванию — то получится битоническая последовательность. Далее мы найдем этому свойству применение.
Битонический сортировщик
Сначала мы построим сеть, которая эффективно сортирует все битонические последовательности — т.н. битонический сортировщик.
ПолуфильтрОсновной элемент битонического сортировщика называется полуфильтром (half-cleaner).
Каждый полуфильтр — сравнивающая сеть единичной глубины, в которой
|
Битонический сортировщикТеперь мы используем полуфильтры для сортировки битонических последовательностей. Как только что было доказано, один полуфильтр разделяет битоническую последовательность на две равные части, одна из которых однородна, а другая сама по себе является битонической последовательностью, причем части расположены в правильном порядке. Тогда мы можем каждую часть снова отправить в полуфильтр вдвое меньшего размера, чем предыдущий. Затем, если нужно, четыре получившихся части снова отправить в полуфильтры и так далее, пока количество проводов в частях больше одного. Так можно построить сеть для числа входов, являющегося степенью . Поскольку каждый вертикальный ряд полуфильтров вдвое сокращает число входов, которые необходимо отсортировать, глубина всей сети равна , где — число входов. |
Объединяющая сеть
Битонический сортировщик находит своё применение в конструкции так называемой объединяющей сети.
Построим объединяющую сеть на основе битонического сортировщика. Для этого рассмотрим наши отсортированные сходные последовательности: Итак, объединяющая сеть является ничем иным как битоническим сортировщиком. Единственное отличие в том, что половина входных проводов расположена в обратном порядке (предполагается, что мы объединяем две сети одного размера в одну). Поэтому первый полуфильтр будет отличаться от остальных — он будет соединять -ый провод не с -ым, а с -ым проводом. Пример объединяющей сети для 8 проводов приведен на рисунке 4. |
Источники
- Wikipedia — Batcher odd-even mergesort
- Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2005. — С. 808—818.