Sieć sortowania parami

Sieć sortowania parami

Wizualizacja sieci sortowania parami z 16 wejściami
Klasa	Algorytm sortowania
Struktura danych	Szyk
Wydajność w najgorszym przypadku	${\ Displaystyle (\ log n) (\ log n + 1)/2}$ czas równoległy
Złożoność przestrzeni w najgorszym przypadku	${\ Displaystyle n (\ log n) (\ log n-1) / 4 + n-1} czas$ nierównoległy

Sieć sortowania parami to sieć sortowania odkryta i opublikowana przez Iana Parberry'ego w 1992 roku w Parallel Processing Letters . Sieć sortowania parami ma taki sam rozmiar (liczba komparatorów) i głębokość jak sieć sortowania nieparzystego i parzystego . W momencie publikacji sieć była jedną z kilku znanych sieci o głębokości . ${\ Displaystyle O (log ^ {2} n)}$ . Wymaga ${\ Displaystyle n (\ log n) (\ log n-1) / 4 + n-1}$ i ma głębokość ${\ Displaystyle (\ log n) (\ log n + 1) / 2}$ .

Procedura sortowania realizowana przez sieć jest następująca (kieruje się zasadą zero-jedynkową ):

1. Sortuj parami kolejne bity wejścia (odpowiada pierwszej warstwie diagramu)
2. Sortuj wszystkie pary w porządku leksykograficznym, rekurencyjnie sortując osobno wszystkie bity nieparzyste i parzyste (odpowiada kolejnym 14 warstwom diagramu)
3. Posortuj pary w porządku niemalejącym za pomocą wyspecjalizowanej sieci (odpowiada końcowym warstwom diagramu)

Relacja do Batchera nieparzyste-parzyste scalanie

Sieć sortowania parami jest bardzo podobna do sortowania nieparzystego-parzystego Batchera, ale różni się strukturą operacji. Podczas gdy Batcher wielokrotnie dzieli, sortuje i łączy coraz dłuższe podsekwencje, metoda parami najpierw dokonuje podziału, a następnie scala na końcu w odwrotnej kolejności. W niektórych zastosowaniach, takich jak kodowanie ograniczeń liczności, sieć sortowania parami jest lepsza od sieci Batchera.

Linki zewnętrzne

• Sorting Networks – Archiwum strony internetowej autorstwa autora.