Sorting Race — wette auf den schnelleren Algorithmus
Zwei Sortieralgorithmen rennen über dasselbe Array. Wette auf den Sieger — die bessere Komplexität verliert öfter als gedacht. Kostenlos.
Sechs Rennen. Dasselbe Array, zwei Algorithmen — tippe auf den, der zuerst fertig ist.
So wird gespielt
- Zwei Sortierer, ein Array. Setze auf den, der zuerst fertig wird, und schau zu.
- Es gewinnt der mit weniger Operationen — Vergleiche plus Bewegungen —, nicht der mit der besseren Lehrbuchkomplexität.
- Lies Größe und Form. Unter etwa zwanzig Balken gewinnen die einfachen; bei einem fast sortierten Array schlägt Insertionsort alles.
- Ein richtiger Tipp zahlt 50, ein falscher kostet 50. Sechs Rennen, und du startest mit 100.
So funktioniert es
Zwei Sortieralgorithmen rennen über dasselbe Array, gezeichnet als Balken, und du wettest darauf, wer zuerst fertig ist. Jede Runde stellt einen O(n log n)-Sortierer gegen einen O(n²)-Sortierer, es gibt also immer einen offensichtlichen Favoriten — und der offensichtliche Favorit liegt ungefähr in der Hälfte der Fälle daneben. Entschieden wird es tatsächlich von der Größe des Arrays und seiner Form: Insertionsort erledigt ein fast sortiertes Array mit einem Zwanzigstel der Operationen, die ein naiver Quicksort braucht, und unterhalb von etwa zwanzig Elementen wiegen die konstanten Faktoren schwerer als die Asymptotik — genau deshalb schalten echte Sortierbibliotheken dort unten auf Insertionsort um. Der Sieger wird über die Zahl der Operationen bestimmt, nicht über eine Stoppuhr, das Ergebnis ist also auf jedem Rechner dasselbe. Läuft auf deinem Gerät, es wird nichts verschickt, und es gibt nichts anzumelden.
Operationen heißt Vergleiche plus Datenbewegungen, wobei ein Tausch einmal zählt, gezählt an schlichten Lehrbuchimplementierungen. Echte Bibliothekssortierer sind Hybride und würden fast jedes Rennen gewinnen — genau darum geht es hier.
Häufig gestellte Fragen
Ist der bessere Algorithmus nicht immer schneller?
Bei diesen Größen nicht. Big-O beschreibt, wie die Kosten wachsen, nicht wie hoch sie sind — und verschweigt den konstanten Faktor völlig. Über 400 Durchläufe gemessen: auf die bessere Lehrbuchkomplexität zu setzen trifft 3,19 von 6, gegenüber 3,00 beim immergleichen Tipp. Zwei Regeln — ein fast sortiertes und ein kleines Array begünstigen beide den einfachen Sortierer — treffen etwa 4,8 von 6.
Wie wird der Sieger bestimmt?
Durch Zählen von Vergleichen und Bewegungen, berechnet bevor irgendetwas gezeichnet wird. Die Animation spielt diese Zahl auf beiden Seiten im selben Takt ab, also kommt die Seite mit weniger Operationen aus demselben Grund zuerst ans Ziel, aus dem sie gewinnt. Ein Visualisierer, der zwei Echtzeitschleifen laufen ließe, gäbe auf einer schnellen Maschine eine andere Antwort als auf einer langsamen.
Warum schneidet Quicksort manchmal so schlecht ab?
Es nimmt das letzte Element als Pivot, die naive Variante. Bei einem bereits oder fast sortierten Array ist das die denkbar schlechteste Wahl, die Partitionen entarten, und es leistet quadratische Arbeit genau bei der Eingabe, die Insertionsort am schnellsten erledigt. Echte Implementierungen wählen Median-of-three oder ein zufälliges Pivot, genau um das zu vermeiden.
Was bedeuten die Array-Formen?
Zufällig ist gemischt. Fast sortiert ist bis auf ein paar benachbarte Vertauschungen in Ordnung. Umgekehrt ist genau falsch herum. Wenige Werte hat nur vier verschiedene Werte — dort fällt die Partition eines naiven Quicksort auseinander. Sägezahn wiederholt dieselbe Rampe mehrfach.