Blatt · Ordnung
Sortiernetz — sortieren ohne hinzusehen
Jedes Sortierverfahren, das man kennt, entscheidet unterwegs: Es schaut sich die Daten an und wählt danach, was als Nächstes verglichen wird. Es geht auch anders. Ein Sortiernetz ist eine fest verdrahtete Folge von Vergleichen — immer dieselbe, unabhängig davon, was hineinkommt. Dass so etwas überhaupt funktionieren kann, ist erstaunlich. Dass man mit ein paar hundert Nullen und Einsen beweisen kann, dass es für jede Eingabe funktioniert, ist der eigentliche Trick.
| n | Blasen | ger/ung | Batcher | bekannt bestes |
|---|
Der ganze Bereich hängt an einem Satz: Ein Netz sortiert alle Eingaben genau dann, wenn es alle Eingaben aus Nullen und Einsen sortiert. Das klingt zu billig, um wahr zu sein — deshalb wird es hier nicht geglaubt, sondern nachgerechnet: für zufällige Netze einmal über alle 2ⁿ Nullen-Einsen-Muster und einmal über alle n! Anordnungen.
noch nicht geprüft
Warum Nullen und Einsen genügen
Ein Vergleicher tut nichts anderes, als Minimum und Maximum zu sortieren — und das vertauscht sich mit jeder monotonen Abbildung. Sortiert ein Netz irgendeine Eingabe falsch, kann man alles unterhalb einer Schwelle auf 0 und alles darüber auf 1 abbilden und bekommt ein Nullen-Einsen-Muster, das ebenfalls falsch sortiert wird. Statt n! Anordnungen bleiben 2ⁿ Muster zu prüfen — bei n = 16 sind das 65 536 statt 20 Billionen.
Wozu das gut ist
Weil ein Netz keine Verzweigung braucht. Alles in einer Stufe kann gleichzeitig geschehen — in Schaltungen, auf Grafikkarten, in Rechenwerken, die alle Kerne im Gleichschritt halten. Dort ist nicht die Zahl der Vergleiche entscheidend, sondern die Tiefe: wie viele Stufen nacheinander nötig sind.
Wie schwer das Beste zu finden ist
Bis acht Drähte weiß man es seit den Sechzigern. Für neun und zehn wurde es erst 2014 bewiesen — mit erheblichem Rechenaufwand: 25 und 29 Vergleicher. Ab elf Drähten ist offen, ob es noch besser geht. Die kleine Suche in diesem Blatt findet bis acht Drähte trotzdem genau die bekannten Bestwerte, in Sekundenbruchteilen.
Eine einzelne HTML-Datei. Kein Build, keine Bibliothek, nichts verlässt den Browser. Alle Blätter: ssims437.github.io