Сеть Бетчера

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

Определение

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

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

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

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

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

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

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

Нуль-единичные битонические последовательности - последовательности вида $0^i1^j0^k$ или $1^i0^j1^k$ для $i,j,k\le0$

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

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

Рис.1 Полуфильтр для 8 проводов

Битонический сотрировщик erwtgretasdfg a sdfg sdhgj adfh artfgh DASGASJ DFA HTY ADFHWT YDASGS UJA ZHJRYTUH R DEUJETYH FYUJES SDFGHGS HERFGAHE FGHWRFG YTEUH SHEDT.erwtgretasdfg a sdfg sdhgj adfh artfgh DASGASJ DFA HTY ADFHWT YDASGS UJA ZHJRYTUH R DEUJETYH FYUJES SDFGHGS HERFGAHE FGHWRFG YTEUH SHEDT.erwtgretasdfg a sdfg sdhgj adfh artfgh DASGASJ DFA HTY ADFHWT YDASGS UJA ZHJRYTUH R DEUJETYH FYUJES SDFGHGS HERFGAHE FGHWRFG YTEUH SHEDT.erwtgretasdfg a sdfg sdhgj adfh artfgh DASGASJ DFA HTY ADFHWT YDASGS UJA ZHJRYTUH R DEUJETYH FYUJES SDFGHGS HERFGAHE FGHWRFG YTEUH SHEDT.erwtgretasdfg a sdfg sdhgj adfh artfgh DASGASJ DFA HTY ADFHWT YDASGS UJA ZHJRYTUH R DEUJETYH FYUJES SDFGHGS HERFGAHE FGHWRFG YTEUH SHEDT.erwtgretasdfg a sdfg sdhgj adfh artfgh DASGASJ DFA HTY ADFHWT YDASGS UJA ZHJRYTUH R DEUJETYH FYUJES SDFGHGS HERFGAHE FGHWRFG YTEUH SHEDT.erwtgretasdfg a sdfg sdhgj adfh artfgh DASGASJ DFA HTY ADFHWT YDASGS UJA ZHJRYTUH R DEUJETYH FYUJES SDFGHGS HERFGAHE FGHWRFG YTEUH SHEDT.erwtgretasdfg a sdfg sdhgj adfh artfgh DASGASJ DFA HTY ADFHWT YDASGS UJA ZHJRYTUH R DEUJETYH FYUJES SDFGHGS HERFGAHE FGHWRFG YTEUH SHEDT.erwtgretasdfg a sdfg sdhgj adfh artfgh DASGASJ DFA HTY ADFHWT YDASGS UJA ZHJRYTUH R DEUJETYH FYUJES SDFGHGS HERFGAHE FGHWRFG YTEUH SHEDT.erwtgretasdfg a sdfg sdhgj adfh artfgh DASGASJ DFA HTY ADFHWT YDASGS UJA ZHJRYTUH R DEUJETYH FYUJES SDFGHGS HERFGAHE FGHWRFG YTEUH SHEDT.erwtgretasdfg a sdfg sdhgj adfh artfgh DASGASJ DFA HTY ADFHWT YDASGS UJA ZHJRYTUH R DEUJETYH FYUJES SDFGHGS HERFGAHE FGHWRFG YTEUH SHEDT.erwtgretasdfg a sdfg sdhgj adfh artfgh DASGASJ DFA HTY ADFHWT YDASGS UJA ZHJRYTUH R DEUJETYH FYUJES SDFGHGS HERFGAHE FGHWRFG YTEUH SHEDT.erwtgretasdfg a sdfg sdhgj adfh artfgh DASGASJ DFA HTY ADFHWT YDASGS UJA ZHJRYTUH R DEUJETYH FYUJES SDFGHGS HERFGAHE FGHWRFG YTEUH SHEDT.erwtgretasdfg a sdfg sdhgj adfh artfgh DASGASJ DFA HTY ADFHWT YDASGS UJA ZHJRYTUH R DEUJETYH FYUJES SDFGHGS HERFGAHE FGHWRFG YTEUH SHEDT.erwtgretasdfg a sdfg sdhgj adfh artfgh DASGASJ DFA HTY ADFHWT YDASGS UJA ZHJRYTUH R DEUJETYH FYUJES SDFGHGS HERFGAHE FGHWRFG YTEUH SHEDT.erwtgretasdfg a sdfg sdhgj adfh artfgh DASGASJ DFA HTY ADFHWT YDASGS UJA ZHJRYTUH R DEUJETYH FYUJES SDFGHGS HERFGAHE FGHWRFG YTEUH SHEDT.erwtgretasdfg a sdfg sdhgj adfh artfgh DASGASJ DFA HTY ADFHWT YDASGS UJA ZHJRYTUH R DEUJETYH FYUJES SDFGHGS HERFGAHE FGHWRFG YTEUH SHEDT.erwtgretasdfg a sdfg sdhgj adfh artfgh DASGASJ DFA HTY ADFHWT YDASGS UJA ZHJRYTUH R DEUJETYH FYUJES SDFGHGS HERFGAHE FGHWRFG YTEUH SHEDT.erwtgretasdfg a sdfg sdhgj adfh artfgh DASGASJ DFA HTY ADFHWT YDASGS UJA ZHJRYTUH R DEUJETYH FYUJES SDFGHGS HERFGAHE FGHWRFG YTEUH SHEDT.erwtgretasdfg a sdfg sdhgj adfh artfgh DASGASJ DFA HTY ADFHWT YDASGS UJA ZHJRYTUH R DEUJETYH FYUJES SDFGHGS HERFGAHE FGHWRFG YTEUH SHEDT.erwtgretasdfg a sdfg sdhgj adfh artfgh DASGASJ DFA HTY ADFHWT YDASGS UJA ZHJRYTUH R DEUJETYH FYUJES SDFGHGS HERFGAHE FGHWRFG YTEUH SHEDT.erwtgretasdfg a sdfg sdhgj adfh artfgh DASGASJ DFA HTY ADFHWT YDASGS UJA ZHJRYTUH R DEUJETYH FYUJES SDFGHGS HERFGAHE FGHWRFG YTEUH SHEDT.erwtgretasdfg a sdfg sdhgj adfh artfgh DASGASJ DFA HTY ADFHWT YDASGS UJA ZHJRYTUH R DEUJETYH FYUJES SDFGHGS HERFGAHE FGHWRFG YTEUH SHEDT.erwtgretasdfg a sdfg sdhgj adfh artfgh DASGASJ DFA HTY ADFHWT YDASGS UJA ZHJRYTUH R DEUJETYH FYUJES SDFGHGS HERFGAHE FGHWRFG YTEUH SHEDT.erwtgretasdfg a sdfg sdhgj adfh artfgh DASGASJ DFA HTY ADFHWT YDASGS UJA ZHJRYTUH R DEUJETYH FYUJES SDFGHGS HERFGAHE FGHWRFG YTEUH SHEDT.erwtgretasdfg a sdfg sdhgj adfh artfgh DASGASJ DFA HTY ADFHWT YDASGS UJA ZHJRYTUH R DEUJETYH FYUJES SDFGHGS HERFGAHE FGHWRFG YTEUH SHEDT.erwtgretasdfg a sdfg sdhgj adfh artfgh DASGASJ DFA HTY ADFHWT YDASGS UJA ZHJRYTUH R DEUJETYH FYUJES SDFGHGS HERFGAHE FGHWRFG YTEUH SHEDT.erwtgretasdfg a sdfg sdhgj adfh artfgh DASGASJ DFA HTY ADFHWT YDASGS UJA ZHJRYTUH R DEUJETYH FYUJES SDFGHGS HERFGAHE FGHWRFG YTEUH SHEDT.

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

Источники

• Batcher odd-even merge sort
• Т.Кормен "Алгоритмы построение и анализ"