Parvis sorteringsnätverk

Parvis sorteringsnätverk

Visualisering av Pairwise sorteringsnätverk med 16 ingångar
Klass	Sorteringsalgoritm
Datastruktur	Array
Prestanda i värsta fall	$(\log n)(\log n+1)/2$ parallelltid
Värsta tänkbara rymdkomplexitet	$n(\log n)(\log n-1)/4+n-1$ icke-parallell tid

Det parvisa sorteringsnätverket är ett sorteringsnätverk som upptäcktes och publicerades av Ian Parberry 1992 i Parallel Processing Letters . Det parvisa sorteringsnätverket har samma storlek (antal komparatorer) och djup som det udda-jämna sammanslagna nätverket . Vid tidpunkten för publiceringen var nätverket ett av flera kända nätverk med ett djup på $O(log^{2}n)$ . Den kräver $n(\log n)(\log n-1)/4+n-1$ komparatorer och har djup $(\log n)(\log n+1)/2$ .

Sorteringsproceduren som implementeras av nätverket är som följer (styrd av noll-ett-principen ):

1. Sortera på varandra följande parvisa bitar av ingången (motsvarar det första lagret i diagrammet)
2. Sortera alla par i lexikografisk ordning genom att rekursivt sortera alla udda bitar och jämna bitar separat (motsvarar de nästa 14 lagren i diagrammet)
3. Sortera paren i icke-minskande ordning med hjälp av ett specialiserat nätverk (motsvarar de sista lagren i diagrammet)

Relation till Batcher odd-even mergesort

Det parvisa sorteringsnätverket är mycket likt Batchers udda-jämna sammanslagningssort, men skiljer sig i strukturen av operationer. Medan Batcher upprepade gånger delar upp, sorterar och slår samman allt längre delsekvenser, gör den parvisa metoden all underindelning först, och gör sedan all sammanslagning i slutet i omvänd sekvens. I vissa applikationer som kodningskardinalitetsbegränsningar är det parvisa sorteringsnätverket överlägset Batcher-nätverket.

externa länkar

• Sorteringsnätverk – Arkiv för webbsida av författaren.