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

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

Визуализация сети попарной сортировки с 16 входами
Сорт	Алгоритм сортировки
Структура данных	Множество
Худшая производительность	$(\log n)(\log n+1)/2$ параллельное время
Наихудшая пространственная сложность	$n(\log n)(\log n-1)/4+n-1$ непараллельное время
Оптимальный	Нет

Сеть попарной сортировки — это сеть сортировки, открытая и опубликованная Яном Парберри в 1992 году в журнале Parallel Processing Letters . Сеть попарной сортировки имеет тот же размер (количество компараторов) и глубину, что и сеть нечетно-четной сортировки слиянием . На момент публикации сеть была одной из нескольких известных сетей с глубиной $O(\log ^{2}n)$. Это требует $n(\log n)(\log n-1)/4+n-1$ компараторов и имеет глубину $(\log n)(\log n+1)/2$.

Процедура сортировки, реализуемая сетью, следующая (руководствуется принципом нуля-единицы ):

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

Связь с сортировкой слиянием нечет-чет Бэтчера

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

Внешние ссылки

• Сортировочные сети – Архив веб-страницы автора.