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

Question

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

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

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

Я погуглил это, но не нашел простого объяснения с примером.

Answer 1

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

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

Источник: Университет Лейпцига

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

Название ИМХО получено из графика бабочки, который показан, например, в быстром преобразовании Фурье, этот вид потока данных с пересечением напоминает бабочку.

Источник: Википедия

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