133
правки
Изменения
→Битонический сортировщик
В этой статье будет описана сортирующая сеть для случая когда <tex>n</tex> {{---}} степень двойки (<tex>n =2^k</tex>). =Конструирование сети= Битоническая последовательность ==Для начала Сначала введем понятие битонической последовательности:все необходимые понятия для построения сортирующей сети Бетчера.
{{Определение
|definition=
{{Определение
|definition=
== Битонический сортировщик ==Построим сеть, которая эффективно сортирует все битонические последовательности {{| <!-- Какие-то адовые костыли только чтобы разместить картинку справа от текста -->}} так называемый '''битонический сортировщик''' (англ. ''bitonic sorter''). {|
|
{{Лемма|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 Все случаи попадания битонической последовательности на полуфильтр]]
|}
Так можно построить сеть для числа входов, являющегося степенью <tex>2</tex>двойки. Поскольку каждый вертикальный ряд полуфильтров вдвое сокращает число входов, которые необходимо отсортировать, глубина всей сети равна <tex>\log_{2}n</tex>, где <tex>n</tex> {{---}} число входов.||[[Файл:Bitonic_sorter_8.png|305px|right|thumb|Рис.3 Битонический сортировщик Количество компараторов равно <tex dpi="150">\frac{n \log_2{n}}{2}</tex>, потому что размер одного полуфильтра на 8 <tex>n</tex> входов {{---}} <tex>\dfrac{n}{2}</tex> компараторов, а в слое битонического сортировщика находится <tex>2^{i-1}</tex> полуфильтров, где <tex>i</tex> {{---}} номер слоя, начиная с выделенными полуфильтрамиединицы.]]|}
{{Определение
|definition=
*Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2005. — С. 808—818.
<!-- TODO: проверить 2007 издание Кормена и написать его -->
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортирующие сети]]