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

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

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

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

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

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

Ссылки

1. Парберри, Ян (1992), «Парная сортировочная сеть» (PDF) , Parallel Processing Letters , 2 (2, 3): 205–211, doi :10.1142/S0129626492000337, S2CID  2986739, архивировано из оригинала (PDF) 29 октября 2019 г.
2. «Сортировочные сети».

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

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