Сеть бабочек при сортировке

Question

Я изучаю даже нечетный тип слияния в алгоритмах Роберт Седвик в C++.

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

Мой вопрос в том, что такое в основном сеть бабочек и почему это называется бабочка. Объяснение с простым примером будет оценено.

У меня есть googled, но не найти простое объяснение с примером.

Answer 1

Сеть бабочек - это определенный вид sorting network. Сортировочную сеть можно рассматривать как абстрактную сеть (например, сеть передачи данных) или довольно конкретную как электрическую цепь.

Эти сети состоят из входных и выходных проводов и пары компараторов multiplexers, которые направляют входящие значения от одного провода к другому. Это пример параллельной сортировки.

Источник: Universität Leipzig

В приведенном выше аквалангисты, входы слева набора, то есть на Выходы с правой стороны, квадратные коробки компараторов. Идея состоит в том, что вы можете поместить произвольные значения от 0 до 15 на каждом входе, и они будут перенаправлены на выходы компараторами (которые проверяют входящее значение и решают перейти на другой провод или держать его на одном проводе), все 0 значения будут направляться к верхнему выходу (000), все значения 1 ко второму выходу (001) и т.д.

название ИМХО происходит от butterfly graph, которое будет показано, например, в Fast Fourier Transform, такого рода данных поток с его пересечением перебирает бабочку.

Источник: Wikipedia

Если посмотреть на первой диаграмме сети бабочки, вы видите это повторяется снова и снова.