Interaktives Sortiernetzwerk-Diagramm mit Schritt-fur-Schritt-Animation
Ein Sortiernetzwerk ist ein Komparatornetzwerk mit fester Struktur, das jede Eingabesequenz mit einer vordefinierten Anordnung von Vergleichs- und Vertauschungsoperationen sortiert. Im Gegensatz zu adaptiven Algorithmen wie Quicksort fuhrt ein Sortiernetzwerk unabhangig von den Eingabedaten genau dieselben Vergleiche durch.
Jeder Vergleicher verbindet zwei Leitungen (Positionen i und j) und leitet den kleineren Wert zur oberen Leitung und den grosseren zur unteren. Wenn die Werte bereits in Ordnung sind, andert sich nichts; anderenfalls werden sie vertauscht.
Die Tiefe eines Sortiernetzwerks ist die maximale Anzahl von Schichten von der Eingabe zur Ausgabe. Vergleicher auf derselben Tiefe haben keine Datenabhangigkeiten und konnen gleichzeitig parallel ausgefuhrt werden.
Herkommliche Sortieralgorithmen entscheiden den nachsten Vergleich basierend auf vorherigen Ergebnissen. Sortiernetzwerke bestimmen alle Vergleiche im Voraus, was sie ideal fur Hardware-Implementierung und GPU-Parallelrechnen macht.
Sortiernetzwerke werden weit verbreitet in: GPU-Sortierung (Bitonic Sort ist die Grundlage von CUDA-Sortierung), Hardware-Sortierschaltkreis-Design, Oblivious Sorting in sicherer Berechnung, Datenbankabfrage-Optimierung und Netzwerkpaket-Sortierung.
Fur kleine N sind die bekannten optimalen Vergleicheranzahlen: N=4 erfordert 5 Vergleicher, N=5 braucht 9, N=6 braucht 12, N=7 braucht 16, N=8 braucht 19, N=9 braucht 25, N=10 braucht 29, N=16 braucht 60. Das 0-1-Prinzip beweist, dass die Uberprufung aller 2^N binaren Eingaben ausreicht, um die Korrektheit des Netzwerks zu bestatigen.