Sorteringsnetværk

Et sorteringsnetværk er en abstrakt matematisk model af et netværk af tråde og sammenligningselementer, som bruges til at sortere en sekvens af tal. Hvert sammenligningselement forbinder to tråde og sorterer værdierne ved at fordele det lave tal til den ene tråd og det høje tal til den anden. Hovedforskellen mellem sorteringsnetværk og sorteringsalgoritmer, der ligledes sammenligner værdier med hinanden, er at rækkefølgen af sammenligninger i et sorteringsnetværk er sat på forhånd, uafhængigt af tidligere resultater. Denne uafhængige sekvens af sammenligninger er særdeles brugbar ved parallel udførsel af algoritmen. Dog skal det nævnes at teorien bag sorteringsnetværk er overraskende kompleks på trods af den simple model.

Introduktion 

Et sorteringsnetværk består af to dele: sammenligningselementer og tråde. Hver tråd er tilknyttet en værdi og hvert sammenligningselement indlæser og udlæser to tråde. Når to værdier kommer ind i sammenligningselementet vil den lave værdi blive placeret på øvre tråd, og den høje værdi vil blive placeret på den nedre tråd. Et netværk af tråde og sammenligningselementer som på korrekt vis vil sorterer alle mulige inddata i stigende rækkefølge, kaldes for et sorteringsnetværk.

Den fulde udførelse af et simpelt sorteringsnetværk er vist forneden. Det er nemt at se hvorfor dette sorteringsnetværk vil sorterer værdierne korrekt, fordi de første fire sammenligningselementer vil "sænke" det højeste tal til bunden, og "hæve" det laveste tal til toppen. Det sidste sammenligningselement vil sorterer de midterste to tråde.

Indsættelses- og udvalgsnetværk 
Vi kan vent konstruere et netværk af en hvilken som helst størrelse ved gentagende gange at benytte indsættelses- og udvalgsprincipperne. Hvis vi udgår fra at vi har et sorteringsnetværk på størrelsen n, kan vi konstruere et netværk på størrelse  ved at "indsætte" endnu et tal til et netværk der allerede er sorteret subnetværk (ved at bruge principperne omkring indsættelsessortering). Vi kan også opnå det samme resultat ved først at "udvælge" den laveste værdi fra inddataene og så sortere de resterende værdier gentagende gange (ved at bruge principperne bag boblesortering).

Strukturen på disse to sorteringsnetværk er meget lignende hinanden. En konstruktion af de to varianter, som samler de sammenligningselementer som kan sammenligne elementer samtidigt, viser at de to varianter faktisk er identiske.

Effektive netværk 
Indsættelsesnetværket har en stor dybde på O(n) hvilket gør den upraktisk. Der er netværk som er mere simple, som opnår en dybde på O((log n)2) (ergo en størrelse på  så som Batcher odd-even mergesort, bitonic sort, Shell sort, og Pairwise sorting network. Disse netværk bruges ofte i paksis.

Nul-et-princippet 
Selv om det er nemt nok at validere nogle sorteringsnetværk (så som indsættelses- og boblesortering), er det ikke altid lige let. Der er n! ombytninger af tal i et n-trådsnetværk, og at skulle teste dem alle ville tage lang tid, især når de er store. Heldigvis skal der langt færre afprøvninger til for at validere et sorteringsnetværk takket være det såkaldte nul-et-princip.

Nul-et-princippets definition er at et sorteringsnetværk er gyldigt hvis det kan sortere alle 2n sekvenser af 0- og 1-taller. Dette ikke kun drastisk reducerer antallet af nødvendige tests for at validere et netværk, men det bruges også til at fremstille mange konstruktioner af sorteringsnetværk. Princippet er blevet bevist i forbindelse med Bouricius's Theorem i 1954 af W. G. Bouricius.

Optimal sortering 
Effektiviteten af et sorteringsnetværk kan måles i den totale størrelse (antallet af sammenligningselementer), eller i dens dybde (det højeste antal af sammenligningselementer til en hvilken som helst tråd fra inddata til uddata). Det mest asymptotisk optimale sorteringsnetværk man kender hedder et AKS-netværk, opkaldt efter dets opdagere Ajtai, Komlós og Szemerédi, opnår en dybde på O(log n) og størrelsen  for n inddata. På trods af at ASK-netværket var en teoretisk vigtig opdagelse, har det i praksis næsten ingen anvendelse på grund af den høje konstant der er gemt i Store-O notationen. Det er endnu ikke lykkedes at finde et sorteringsnetværk med størrelsen  for et lille c.

Visse vigtige fremskridt i at designe de mest optimale sorteringsnetværk sker ved hjælp af en genetisk algoritme.

For 1 til 8 inddata, kendes det mest optimale sorteringsnetværk allerede. De har hhv. 0, 1, 3, 5, 9, 12, 16 og 19 sammenligningskomponenter (Knuth, 1997). Den mest optimale dybde for op til 10 inddata er ligledes kendt og er hhv. 0, 1, 3, 3, 5, 5, 6, 6, 7, 7.

Referencer 
 O. Angel, A.E. Holroyd, D. Romik, B. Virag, Random Sorting Networks, Adv. in Math., 215(2):839–868, 2007.
 K.E. Batcher, Sorting networks and their applications, Proceedings of the AFIPS Spring Joint Computer Conference 32, 307–314 (1968).
 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 1990. . Chapter 27: Sorting Networks, pp.704–724.
 D.E. Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. . Section 5.3.4: Networks for Sorting, pp. 219–247.
 .
 M. S. Paterson, Improved sorting networks with O(log N) depth, Algorithmica 5 (1990), no. 1, pp. 75–92, .
 M. Mitchell, An Introduction to Genetic Algorithms, The MIT Press, 1998. . Chapter 1: Overview, pp. 21–27
 Alex Peter, Retrograde Software Analysis, UniBook, 2010, pp. 8-13

Eksterne henvisninger 
 Sorting Networks 
 Sorting Networks 
 List of Sorting Networks 
 Sorting networks and the END algorithm

Computernetværk
Sorteringsalgoritmer