Sortieralgorithmen-Wettrennen

verfolge Schritt für Schritt zwei Algorithmen im Wettrennen auf derselben Eingabe — Vergleiche, Swaps, Komplexität

Interaktive Simulation wird geladen...

Big O ist nicht die ganze Geschichte 🖖

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.

Warum Schritte statt Sekunden zählen 🖖

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.

Quicksort entstand beim Russisch-Übersetzen 🖖

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.

Aufgabe vollständig gelöst

Genaue Vorhersage der Anzahl der Vertauschungen bei Bubble Sort für 64 umgekehrte Elemente 7 Schritte
Führen Sie das Rennen mit der Voreinstellung umgekehrt aus — 64 Elemente, das größte zuerst. Sagen Sie die Anzahl der Vertauschungen von Bubblesort exakt voraus, nicht seine Wachstumsordnung; erklären Sie dann, was jeden Algorithmus, der nur Nachbarn tauscht, daran hindert, dieses Ergebnis zu unterbieten.
1. Eine Inversion ist ein Paar, das in der falschen relativen Reihenfolge steht. Eine umgekehrte Eingabe ist der Extremfall: Für jedes i < j ist das frühere Element das größere, sodass jedes Paar invertiert ist und ihre Anzahl der Gesamtzahl aller Paare entspricht. Bestimmen Sie diese Zahl, bevor sich irgendetwas bewegt — sie erweist sich als das gesamte Problem.
  
  $I = # {(i, j) : i < j, a_{i} > a_{j}} = (2 64) = \frac{64 \times 63}{2} = 2, 016$
2. Bubblesort tauscht nur benachbarte Elemente, und das auch nur, wenn sie nicht sortiert sind. Ein solcher Tausch korrigiert genau dieses eine Paar und stört kein anderes, da die zwei bewegten Elemente dieselbe Beziehung zu allem außerhalb behalten. Eine Vertauschung, eine Inversion — niemals zwei, niemals keine.
  
  $a_{k} > a_{k + 1} ⟶ I \mapsto I - 1$
3. Sortiert bedeutet null Inversionen. Bei 2.016 zu beginnen und pro Vertauschung genau eine zu entfernen, lässt keinen Spielraum: Die Anzahl der Vertauschungen ist erzwungen. Das Bedienfeld gibt 2.016 Vertauschungen aus, und das ist eine Identität und nicht bloß eine Worst-Case-Schranke.
  
  $S = I_{0} - 0 = 2, 016$
4. Vergleiche sind eine eigene Zählung, die hier zufällig übereinstimmt. Durchlauf i prüft j = 0 … 62 − i, sodass die Summe 63 + 62 + ⋯ + 1 beträgt — dieselbe 2.016, die die Zeile Bubble Worst-Case n(n−1)/2 zeigt. Gleiche Anzahlen bedeuten, dass jeder einzelne Vergleich eine Inversion gefunden hat, was hier „Worst Case“ bedeutet. Der Zähler unter dem Titel jedes Bedienfelds zählt einen Schritt pro Vergleich plus einen pro Vertauschung, sodass er vor dem Start Schritt 0 / 4.032 anzeigt, und die Schaltfläche › verbraucht genau einen dieser Schritte pro Klick. Das O(n²) neben dem Titel ist eine Beschriftung, kein Zähler.
  
  $C = i = 0 \sum 62 (63 - i) = 63 + 62 + \dots + 1 = \frac{63 \times 64}{2} = 2, 016 = \frac{n ( n - 1 )}{2}, C + S = 4, 032$
5. Generalisieren Sie nun Schritt 2, denn genau das nutzt Quicksort aus. Das Vertauschen zweier Einträge im Abstand von d Positionen lässt jedes Paar, das mit einem Element außerhalb der Spanne gebildet wird, in der Summe unangetastet: Ein solches Element wird erneut mit dem anderen Ende verglichen, die zwei Vergleiche tauschen die Plätze und sein Beitrag bleibt unverändert. Was sich bewegen kann, ist das Paar selbst sowie die 2(d − 1) Paare, die jedes Ende mit den d − 1 Einträgen dazwischen bildet. Höchstens 2d − 1 Inversionen können pro Tausch verschwinden, und das Setzen von d = 1 liefert wieder die einzelne Inversion aus Schritt 2.
  
  $1 + 2 (d - 1) = 2 d - 1 (d = 1 \Rightarrow 1)$
6. Die erste Partitionierung von Quicksort wählt das mittlere Element als Pivot, a[31] = 33, und tauscht (0, 63), (1, 62), … , (31, 32) — 32 Vertauschungen in den Abständen 63, 61, … , 1. Schritt 5 begrenzt ihre kombinierte Wirkung auf 2.016 Inversionen, und dieser einzelne Durchlauf hinterlässt das Array vollständig sortiert, sodass genau 2.016 entfernt wurden. Die Obergrenze wird mit Gleichheit erreicht: Jede der 32 Vertauschungen hat ihr eigenes Maximum erzielt.
  
  $p = a_{31} = 33, d = 63, 61, \dots, 1 : m = 1 \sum 32 (2 (2 m - 1) - 1) = m = 1 \sum 32 (4 m - 3) = 2, 112 - 96 = 2, 016$
7. Die beiden Algorithmen konkurrieren also nicht in der Klugheit, sondern in der Reichweite. Die für Quicksort angezeigten 334 Vergleiche und 64 Vertauschungen ergeben in der Summe 398 auf seinem Zähler — und nur 32 dieser Vertauschungen bewegen tatsächlich etwas, während die anderen 32 das Pivot betreffen, das in bereits sortierten Abschnitten mit sich selbst getauscht wird. Seine 334 liegen zudem unter der angezeigten n·log₂n-Referenz von 384, da das mittlere Element einer umgekehrten Folge ihr Median ist und somit jede Aufteilung gleichmäßig erfolgt.
  
  $334 + 64 = 398, 64 lo g_{2} 64 = 384, \frac{2 , 016}{32} = 63$
Antwort

2.016 Vertauschungen und 2.016 Vergleiche — die 4.032 Schritte auf dem Zähler. Und 2.016 ist keine reine Eigenschaft von Bubblesort: Es ist eine untere Schranke für eine ganze Familie. Jeder Algorithmus, der darauf beschränkt ist, benachbarte Elemente zu tauschen — Insertionsort, Cocktailshaker-Sort, Gnomesort oder einer, den noch niemand geschrieben hat —, löscht nach Schritt 2 höchstens eine Inversion pro Vertauschung; daher benötigen alle bei dieser Eingabe mindestens 2.016 Vertauschungen und alle liegen bei umgekehrten Daten in Ω(n²), und zwar aufgrund des Modells, in dem sie arbeiten, nicht weil sie ungeschickt wären. Quicksort entkommt dieser unteren Schranke, indem es ihm gestattet ist, ein Element um 63 Positionen auf einmal zu verschieben: 2.016 Inversionen, beseitigt durch 32 echte Vertauschungen, macht 63 Inversionen pro Vertauschung, und Schritt 5 besagt, dass dies das Maximum ist, das eine einzelne Vertauschung über diese Distanz hätte erreichen können. Das Bedienfeld berechnet weder die Anzahl der Inversionen noch die daraus folgende untere Schranke.

$S \geq I_{0} = (2 64) = 2, 016 (d = 1), \frac{I _{0}}{32} = 63$

Lernpfad

Arbeit zählen, nicht Sekunden

Führt zu recursion-tree

Quellen (1)

Insight block 3 — quicksort as its author published it: C. A. R. Hoare, "Quicksort." The Computer Journal 5(1), 10–16, 1962. The algorithm first appeared the year before as C. A. R. Hoare, "Algorithm 64: Quicksort", Communications of the ACM 4(7), 321, 1961.

Vom 42Math-Team · Aktualisiert 2026-05-27

Anhand veröffentlichter Quellen geprüft. Korrekturen willkommen. Redaktionsrichtlinie · Korrekturen

Alle Lektionen: Informatik →

Beispielaufgaben

fast sortiert - Die Eingabeverteilung verändert die relative Effizienz der Algorithmen.
umgekehrt - Bubblesort benötigt 2.016 Vergleiche und 2.016 Vertauschungen: Jeder einzelne Vergleich trifft auf ein unsortiertes Paar, da das Umdrehen von 64 Elementen alle 2.016 Paare auf einmal invertiert. Quicksort erledigt das mit 334 Vergleichen und 64 Vertauschungen und bleibt so unter seiner eigenen n·log₂n-Referenz von 384. Das mittlere Element eines umgedrehten Arrays entspricht nämlich bei jeder Partitionierung exakt dem Median.
wenige unterschiedliche Werte - Achtzig Elemente aus nur acht verschiedenen Werten. Quicksort erfordert 534 Vergleiche gegenüber seiner n·log₂n-Referenz von 506. Dies ist die einzige der drei Voreinstellungen, bei der der Algorithmus oberhalb seiner eigenen Linie landet: Elemente, die dem Pivot gleichen, werden vertauscht, ohne dass dadurch etwas gewonnen wird. Bubblesort führt weiterhin seine festen 3.160 Vergleiche durch, kommt aber mit nur 1.330 Vertauschungen aus, weil so viele benachbarte Paare bereits übereinstimmen.