Sorteringsnätverk är en klass av algoritmiska sorteringsmetoder där sekvensen av jämförelser inte beror på resultaten av tidigare jämförelser.
Ofta avbildad som ett nätverk, de horisontella linjerna i vilka motsvarar överföringen av det sorterade elementet från vänster till höger, och de vertikala anslutningarna av par av linjer indikerar de så kallade "komparatormodulerna", som har två ingångar och två utgångar. Komparatormodulen jämför elementen vid ingången och byter ut dem så att den lägre utgången har till exempel ett större antal. Sorteringsnätverk möjliggör effektiv hårdvaruimplementering.
Det är möjligt att representera olika interna sorteringsalgoritmer som ett sorteringsnätverk.
Topologiskt är strukturen för nätverk skapade på basis av bubbelsorterings- och insättningssorteringsalgoritmer nära. Genom att stapla oberoende komparatormoduler ovanpå varandra kan du få ett nätverk som utför flera jämförelser samtidigt.
Sorteringsalgoritmer | |
---|---|
Teori | Komplexitet O notation Orderförhållande Sorteringstyper hållbar Inre Extern |
Utbyta | |
Val | |
skär | |
fusion | |
Inga jämförelser | |
hybrid | |
Övrig | |
opraktisk |