Сеть попарной сортировки - Pairwise sorting network

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

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

В попарная сортировочная сеть это сортировочная сеть обнаружен и опубликован Яном Парберри в 1992 году в Письма параллельной обработки.^[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. Отсортируйте пары в порядке неубывания с помощью специализированной сети (соответствует последним слоям диаграммы)

Псевдокод

Учитывая количество п элементов для сортировки, это один из возможных нерекурсивных методов вычисления значений индекса элементов для сортировки:

  # задано положительное целое число n, которое является количеством элементов для сортировки # примечание: индексы нумеруются от 0 до (n-1) a = 1; while (a  0) d = e; while (d> 0) b = (d + 1) * ac = 0 while (b 

Отношение к нечетно-четному слиянию Batcher

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

Рекомендации

1. Парберри, Ян (1992), «Сеть парной сортировки» (PDF), Письма параллельной обработки, 2 (2, 3): 205–211
2. http://ianparberry.com/research/sortingnetworks/

внешняя ссылка

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