133
правки
Изменения
→Битонический сортировщик
В этой статье будет описана сортирующая сеть для случая когда <tex>n</tex> {{---}} степень двойки (<tex>n =2^k</tex>). =Конструирование сети= Битоническая последовательность ==Для начала Сначала введем понятие битонической последовательности:все необходимые понятия для построения сортирующей сети Бетчера.
{{Определение
|definition=
{{Определение
|definition=
{| <!-- Какие-то адовые костыли только чтобы разместить картинку справа от текста -->
|
{{Лемма|statement=
Если на вход в полуфильтр подать битоническую последовательность из нулей и единиц длиной <tex>n</tex>, то на выходе мы получим две битонические последовательности длиной <tex>\fracdfrac{n}{2}</tex> такие, что каждый элемент из верхней последовательности не превосходит любой элемент из нижней, и что одна из них будет <b>'''однородной''</b> ' (англ. ''clean'') {{---}} целиком состоящей либо из нулей, либо из единиц.<br><!-- TODO: написать нормальное доказательство, а не копипасту из Кормена -->
|proof=
Для всех <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|РисПолуфильтр для 8 проводов.2 Все случаи попадания битонической последовательности на полуфильтр]]
|}
<references />==Источникиинформации==*[http[wikipedia://en.wikipedia.org/wiki/Batcher_odd-even_mergesort Bitonic_sorter | Wikipedia {{---}} Batcher odd-even mergesortBitonic sorter]]
*Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2005. — С. 808—818.
<!-- TODO: проверить 2007 издание Кормена и написать его -->
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортирующие сети]]