Введение
Абстрактные устройства, состоящие из фиксированного числа "проводов", несущих значения.
В компьютерной науке сравнительные сети — это абстрактные устройства, состоящие из фиксированного числа "проводов", несущих значения, и модулей сравнения, которые соединяют пары проводов, меняя значения на проводах местами, если они расположены не в желаемом порядке. Такие сети обычно разрабатываются для сортировки фиксированного числа значений, в этом случае они называются сортировочными сетями. Сортировочные сети отличаются от общих алгоритмов сортировки сравнением тем, что они не могут обрабатывать произвольно большие входные данные, и тем, что последовательность их сравнений задается заранее, независимо от результатов предыдущих сравнений. Для сортировки большего объема входных данных необходимо создавать новые сортировочные сети. Эта независимость последовательностей сравнений полезна для параллельного выполнения и реализации в аппаратном обеспечении. Несмотря на простоту сортировочных сетей, их теория удивительно глубока и сложна. Сортировочные сети впервые были изучены примерно в 1954 году Армстронгом, Нельсоном и О’Коннором.
Сортировочные сети могут быть реализованы как в аппаратном, так и в программном обеспечении. Дональд Кнут описывает, как сравнители для двоичных целых чисел можно реализовать в виде простых трехпозиционных электронных устройств. С 2000-х годов сортировочные сети (особенно битоничная сортировка слиянием) используются сообществом GPGPU для построения алгоритмов сортировки, предназначенных для работы на графических процессорах.
Введение
Сеть сортировки состоит из двух типов элементов: компараторов и проводов. Провода рассматриваются как идущие слева направо, переносящие значения (по одному на провод), которые одновременно проходят через всю сеть. Каждый компаратор соединяет два провода. Когда пара значений, движущаяся по двум проводам, встречает компаратор, компаратор меняет значения местами, если и только если значение верхнего провода больше или равно значению нижнего провода. Если верхний провод несет значение x, а нижний – значение y, то после прохождения через компаратор провода будут нести значения и соответственно, таким образом, пара значений будет отсортирована. Сеть проводов и компараторов, которая правильно сортирует все возможные входные данные по возрастанию, называется сортировочной сетью или хабом Крускала. Отразив сеть, можно также сортировать все входные данные по убыванию. Полная работа простой сортировочной сети показана ниже. Понятно, почему эта сортировочная сеть правильно сортирует входные данные; обратите внимание, что первые четыре компаратора "опускают" наибольшее значение вниз и "поднимают" наименьшее значение вверх. Последний компаратор сортирует два средних провода.
Глубина и эффективность
Эффективность сортировочной сети можно измерить ее общим размером, то есть количеством компараторов в сети, или ее глубиной, определяемой (неформально) как наибольшее количество компараторов, с которыми может встретиться любое входное значение при прохождении через сеть. Учитывая, что сортировочные сети могут выполнять определенные сравнения параллельно (что в графическом представлении отображается компараторами, расположенными на одной вертикальной линии), и предполагая, что все сравнения занимают единицу времени, можно заключить, что глубина сети равна количеству временных шагов, необходимых для ее выполнения. Несмотря на то, что это важное теоретическое открытие, сеть AKS имеет очень ограниченное практическое применение из-за большой линейной константы, скрытой в нотации «Большого О». Более поздняя конструкция, известная как зигзагообразная сортировочная сеть размером O(n log n), была разработана Гудричем в 2014 году. Хотя ее размер значительно меньше, чем у сетей AKS, ее глубина O(n log n) делает ее непригодной для параллельной реализации.