Интерактивная диаграмма сортирующих сетей с пошаговой анимацией
Сортирующая сеть — это сеть компараторов с фиксированной структурой, которая сортирует любую входную последовательность с помощью предопределённого набора операций сравнения и обмена. В отличие от адаптивных алгоритмов, таких как быстрая сортировка, сортирующая сеть выполняет одни и те же сравнения независимо от входных данных.
Каждый компаратор соединяет две линии (позиции i и j) и направляет меньшее значение на верхнюю линию, а большее — на нижнюю. Если значения уже упорядочены, ничего не меняется; в противном случае они обмениваются местами.
Глубина сортирующей сети — это максимальное число слоёв от входа до выхода. Компараторы на одной глубине не имеют зависимостей по данным и могут выполняться одновременно параллельно.
Традиционные алгоритмы сортировки решают следующее сравнение на основе предыдущих результатов. Сортирующие сети предопределяют все сравнения заранее, что делает их идеальными для аппаратной реализации и параллельных вычислений на GPU.
Сортирующие сети широко используются в: сортировке на GPU (битонная сортировка — основа сортировки CUDA), проектировании аппаратных сортирующих схем, нечувствительной сортировке в безопасных вычислениях, оптимизации запросов к базам данных и сортировке сетевых пакетов.
Для малых N известны оптимальные количества компараторов: N=4 требует 5 компараторов, N=5 — 9, N=6 — 12, N=7 — 16, N=8 — 19, N=9 — 25, N=10 — 29, N=16 — 60. Принцип 0-1 доказывает, что для подтверждения корректности сети достаточно проверить все 2^N двоичных входов.