Síť pro párové párování - Pairwise sorting network
Vizualizace třídicí sítě Pairwise se 16 vstupy | |
Třída | Algoritmus řazení |
---|---|
Datová struktura | Pole |
Nejhorší případ výkon | paralelní čas |
Nejhorší případ složitost prostoru | neparalelní čas |
The síť pro párové třídění je třídicí síť objeven a publikován Ianem Parberrym v roce 1992 v Paralelní zpracování dopisů.[1] Síť párového třídění má stejnou velikost (počet komparátorů) a hloubku jako síť lichá-sudá sloučená síť. V době vydání byla síť jednou z několika známých sítí s hloubkou . To vyžaduje komparátory a má hloubku .
Postup třídění implementovaný sítí je následující (řídí se princip nula jedna ):
- Třídit po sobě jdoucí párové bity vstupu (odpovídá první vrstvě diagramu)
- Řadit všechny páry do lexikografického pořadí rekurzivním tříděním všech lichých a sudých bitů zvlášť (odpovídá dalším 14 vrstvám diagramu)
- Seřaďte páry v neklesajícím pořadí pomocí specializované sítě (odpovídá konečným vrstvám diagramu)
Pseudo kód
Vzhledem k počtu n prvků k třídění, toto je jedna možná nerekurzivní technika pro výpočet indexových hodnot prvků k třídění:
# dané kladné celé číslo n, což je počet prvků k seřazení # poznámka: dolní indexy jsou číslovány od 0 do (n-1) a = 1; while (a 0) d = e; while (d> 0) b = (d + 1) * ac = 0 while (b
Vztah k Batcher liché-sudé sloučení
Síť párového třídění je velmi podobná Batcherovu lichému sudému sloučení, ale liší se ve struktuře operací. Zatímco Batcher opakovaně dělí, třídí a slučuje stále delší subsekvence, metoda pairwise nejprve provede všechny dělení a poté provede všechny slučování na konci v opačném pořadí. V určitých aplikacích, jako je omezení kódování mohutnosti, je síť párového třídění lepší než síť Batcher.[2]
Reference
- ^ Parberry, Ian (1992), „Síť párování Pairwise“ (PDF), Paralelní zpracování dopisů, 2 (2, 3): 205–211
- ^ http://ianparberry.com/research/sortingnetworks/
externí odkazy
- Třídění sítí - Archiv webových stránek autora.
Tento algoritmy nebo datové struktury související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to. |