Сортировочная сеть

A простая сортировочная сеть, состоящая из четырех проводов и пяти соединителей

В информатике, сети компараторов представляют собой абстрактные устройства, состоящие из фиксированного числа «проводов», переносящих значения и компаратора модули, которые соединяют пары проводов, меняя местами значения на проводах, если они расположены не в желаемом порядке. Такие сети обычно предназначены для выполнения сортировки по фиксированному количеству значений, и в этом случае они называются сетями сортировки .

Сети сортировки отличаются от обычных сортировок сравнения тем, что они не способны обрабатывать произвольно большие входные данные, и их последовательность сравнений задается заранее, независимо от результата предыдущих сравнений. Для сортировки большего количества входов необходимо построить новые сети сортировки. Эта независимость сравнительных последовательностей полезна для параллельного выполнения и для реализации в аппаратном обеспечении. Несмотря на простоту сортировочных сетей, их теория на удивление глубока и сложна. Сортировочные сети были впервые изучены примерно в 1954 году Армстронгом, Нельсоном и О'Коннором, которые впоследствии запатентовали эту идею.

Сортировочные сети могут быть реализованы либо в аппаратном обеспечении, либо в программном обеспечении. Дональд Кнут описывает, как компараторы для двоичных целых чисел могут быть реализованы в виде простых электронных устройств с тремя состояниями. Батчер в 1968 году предложил использовать их для построения коммутационных сетей для компьютерного оборудования, заменив обе шины и более быстрые, но более дорогие переключатели с перекладиной. С 2000-х годов сети сортировки (особенно bitonic mergesort ) используются сообществом GPGPU для построения алгоритмов сортировки для работы на графических процессорах.

• 1 Введение
  • 1.1 Глубина и эффективность
  • 1.2 Вставные и пузырьковые сети
  • 1.3 Принцип нуля и единицы
• 2 Построение сетей сортировки
  • 2.1 Оптимальные сети сортировки
  • 2.2 Сложность тестирования сетей сортировки
• 3 Ссылки
• 4 Внешние ссылки

Демонстрация компаратора в сортировочной сети.

Сортировочная сеть состоит из двух типов элементов: компараторов и проводов. Считается, что провода проходят слева направо, передавая значения (по одному на провод), которые проходят через сеть одновременно. Каждый компаратор соединяет два провода. Когда пара значений, проходящая через пару проводов, встречает компаратор, компаратор меняет местами значения тогда и только тогда, когда значение верхнего провода больше или равно значению нижнего провода.

В формуле, если верхний провод несет x, а нижний провод несет y, то после попадания в компаратор провода несут $x\; \prime \; =\; min\; (x,\; y)\; \{\backslash \; displaystyle\; x\; \text{'}=\; \backslash \; min\; (x,\; y)\}$и $y\; \prime \; =\; max\; (x,\; y)\; \{\backslash \; displaystyle\; y\; \text{'}=\; \backslash \; max\; (x,\; y)\}$соответственно, поэтому пара значений отсортирована. Сеть проводов и компараторов, которая будет правильно сортировать все возможные входы в порядке возрастания, называется сетью сортировки или хабом Краскала. Отражая сеть, также можно отсортировать все входные данные в порядке убывания.

Полная работа простой сортировочной сети показана ниже. Очевидно, почему эта сортировочная сеть будет правильно сортировать входы; обратите внимание, что первые четыре компаратора «опускают» наибольшее значение вниз и «перемещают» наименьшее значение вверх. Последний компаратор перебирает два средних провода.

Глубина и эффективность

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

Вставка и пузырьковые сети

Мы можем легко построить сеть любого размера рекурсивно, используя принципы вставки и выбора. Предполагая, что у нас есть сортировочная сеть размера n, мы можем построить сеть размером n + 1, «вставив» дополнительный номер в уже отсортированную подсеть (используя принцип, лежащий в основе insert sort ). Мы также можем сделать то же самое, сначала «выбрав» наименьшее значение из входных данных, а затем рекурсивно отсортировав оставшиеся значения (используя принцип пузырьковой сортировки ).

Сеть сортировки, построенная рекурсивно, которая сначала опускает наибольшее значение в снизу, а затем сортирует оставшиеся провода. На основе пузырьковой сортировки

сеть сортировки, построенная рекурсивно, которая сначала сортирует первые n проводов, а затем вставляет оставшееся значение. На основе сортировка вставкой

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

Сеть пузырьковой сортировки

Сеть сортировки вставкой

При использовании параллельных компараторов пузырьковая сортировка и сортировка вставкой идентичны

Сеть вставки (или, что эквивалентно, пузырьковая сеть) имеет глубину 2n - 3, где n - количество значений. Это лучше, чем O (n log n) время, необходимое машинам с произвольным доступом, но оказывается, что существуют гораздо более эффективные сети сортировки с глубиной всего O (log n), как описано ниже.

Принцип нуля и единицы

Хотя доказать правильность некоторых сетей сортировки (например, вставки / пузырькового сортировщика) несложно, это не всегда так просто. Нет! перестановки чисел в n-проводной сети, и для их проверки потребуется значительное количество времени, особенно когда n велико. Количество тестовых примеров можно значительно сократить до 2, используя так называемый принцип нуля или единицы. Хотя он все еще экспоненциальный, он меньше n! для всех n ≥ 4, и разница довольно быстро растет с увеличением n.

Принцип нуля или единицы гласит, что если сеть сортировки может правильно отсортировать все 2 последовательности нулей и единиц, то он также действителен для произвольно упорядоченных входных данных. Это не только резко сокращает количество тестов, необходимых для проверки достоверности сети, но и очень полезно при создании множества конструкций сетей сортировки.

Принцип может быть доказан, сначала наблюдая следующий факт о компараторах: когда монотонно возрастающая функция применяется к входам, то есть x и y заменяются на f (x) и f (y), то компаратор выдает min (f (x), f (y)) = f (min (x, y)) и max (f (x), f (y)) = f (max ( х, у)). Посредством индукции по глубине сети этот результат может быть расширен до леммы, утверждающей, что если сеть преобразует последовательность a 1,..., a n в b 1,..., b n, он преобразует f (a 1),..., f (a n) в f (b 1),..., f (b n). Предположим, что некоторые входные данные a 1,..., a n содержат два элемента a i< aj, и сеть неправильно меняет местами их на выходе. Тогда он также будет неправильно отсортировать f (a 1),..., f (a n) для функции

$f\; (x)\; =\; \{1\; if\; x>ai\; 0\; в\; противном\; случае.\; \{\backslash \; displaystyle\; f\; (x)\; =\; \{\backslash \; begin\; \{cases\}\; 1\; \backslash \; \{\backslash \; t\_dv\; \{if\}\}\; x>a\_\; \{i\}\; \backslash \backslash \; 0\; \backslash \; \{\backslash \; t\_dv\; \{в\; противном\; случае.\}\}\; \backslash \; end\; \{cases\}\}\}$

Эта функция является монотонной, поэтому у нас есть принцип нуля или единицы в качестве противоположных.