Sortieralgorithmen-Wettrennen

Bubble Sort macht im schlechtesten Fall genau n(n−1)/2 Vergleiche — etwa 2.000 bei n=64. Jeder Durchlauf muss den gesamten verbleibenden unsortierten Bereich absuchen, ohne vorzeitig aussteigen zu können. Die Partitionierung von Quicksort setzt den Pivot an seine endgültige Position und teilt das Problem in zwei Teilprobleme; jede Rekursionsebene leistet O(n) Arbeit über O(log n) Ebenen, macht zusammen O(n log n). Der Haken: Landet der Pivot immer an einem Ende — etwa bei sortierter Eingabe mit dem letzten Element als Pivot — verschlechtert sich die Partitionierung zu n Teilproblemen der Größe n−1, n−2, ..., die sich zu O(n²) aufsummieren. Der hier verwendete Pivot in der Mitte vermeidet das, weshalb umgekehrte Eingaben schnell bleiben. Wenige unterschiedliche Werte sind der interessante Fall: Wenn viele Elemente gleich dem Pivot sind, verschwendet das Vertauschen identischer Werte Arbeit und kann in Richtung quadratisch drücken. Big O verrät dir die Wachstumsklasse; Konstanten, Eingabesensitivität und Cache-Verhalten entscheiden, welchen Algorithmus du tatsächlich einsetzt.

Dieses Rennen bewertet jeden Algorithmus, indem es Vergleiche und Vertauschungen zählt, nicht mit einer Stoppuhr. Die tatsächlich vergangene Zeit hängt von deiner CPU, dem Browser und anderen laufenden Programmen ab, sodass derselbe Code auf verschiedenen Rechnern schnell oder langsam wirken kann. Das Zählen von Operationen liefert ein sauberes, reproduzierbares Maß für die tatsächliche Arbeit: Dieselbe Eingabe ergibt stets dieselben Werte, sodass du die Algorithmen selbst vergleichst und nicht die Hardware.

Tony Hoare erfand Quicksort 1959 als Gaststudent in Moskau, wo er an einem Projekt zur maschinellen Übersetzung arbeitete. Um einen russischen Satz im Wörterbuch nachzuschlagen, musste er dessen Wörter zuerst alphabetisch ordnen — und die übliche Methode war hoffnungslos langsam. Seine Lösung, das Aufteilen um ein Pivot-Element, wurde zu einem der meistgenutzten Algorithmen überhaupt. Die Balken, die hier um die Wette laufen, gehen auf ein Sprachproblem zurück, nicht auf ein Rechenproblem.