Sorteringsnetværk

Et simpelt sorteringsnetværk består af fire tråde og fem sammenligningselementer

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

Demonstration af et sammenligningselement i et sorteringsnetværk.

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 n + 1 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).

Et sorteringsnetværk konstrueret således at det først sænker den højeste værdi til den laveste tråd, og dernæst sorterer det resterende netværk af tråde. Basseret på boblesortering

Et sorteringsnetværk konstrueret således at det først sorterer de n første tråde, og derefter indsætter de resterende værdier. Basseret på indsættelsessortering .

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.

Bubble sorting network

Insertion sorting network

Når man tillader parallelle sammenligninger er boblesortering og indsættelsessortering 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)²) (ergo en størrelse på O(n (log n)²)), 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 2ⁿ 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 O(n log n) 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 cn log n 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. ISBN 0-262-03293-7. 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. ISBN 0-201-89685-0. Section 5.3.4: Networks for Sorting, pp. 219–247.
• Ajtai, M.; Komlós, J.; Szemerédi, E. (1983), "An O(n log n) sorting network", Proceedings of the 15th Annual ACM Symposium on Theory of Computing, s. 1-9, doi:10.1145/800061.808726, ISBN 0897910990.
• 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. ISBN 0-262-63185-7. Chapter 1: Overview, pp. 21–27
• Alex Peter, Retrograde Software Analysis, UniBook, 2010, pp. 8-13

Eksterne henvisninger

• Sorting Networks Arkiveret 27. september 2011 hos Wayback Machine
• Sorting Networks Arkiveret 16. januar 2008 hos Wayback Machine
• List of Sorting Networks Arkiveret 27. september 2011 hos Wayback Machine
• Sorting networks and the END algorithm