powered by 
Fünf Verfahren, die eine Liste durch Vergleichen sortieren: Selection Sort, Insertion Sort, Bubble Sort, Merge Sort und Quick Sort. Zu jedem die Idee, was nach jedem Schritt gilt, der Pseudocode zum Übersetzen in deine Sprache, ein Beispiel zum Durchklicken und typische Fehler. Am Ende ein Vergleich, wie viele Vergleiche jedes Verfahren braucht, wenn die Liste länger wird.
Alle Verfahren auf dieser Seite sortieren nur, indem sie zwei Elemente vergleichen und Elemente schreiben oder vertauschen. Wie schnell ein Verfahren ist, misst man deshalb nicht in Sekunden, sondern zählt Vergleiche und Schreibzugriffe; die Sorting Sandbox zählt genau so. Wichtig ist, wie die Zahl wächst, wenn die Liste länger wird: Bei \(n^2\) Vergleichen braucht eine zehnmal so lange Liste hundertmal so viele, bei \(n \log_2 n\) nur gut dreizehnmal so viele.
Jedes Verfahren hat einen Satz, der nach jedem Schritt stimmt, die Invariante: »Links von Index i ist alles sortiert«, »Rechts von end stehen die größten, an ihrem Platz«. Wer seinen Code so schreibt, dass dieser Satz nie falsch wird, findet die meisten Fehler, bevor sie passieren. Im Beispiel zum Durchklicken ist der Teil lila, für den die Invariante schon gilt.
Alle Beispiele sortieren dieselben acht Zahlen: 5, 2, 8, 1, 9, 3, 7, 4. Über jedem Beispiel kannst du andere acht wählen: schon sortiert, fast sortiert, umgekehrt sortiert oder mit vielen gleichen. Sieh am Ende auf die Zahl der Vergleiche: Bei welchen Verfahren ändert sie sich, bei welchen nicht?
Ein Verfahren ist stabil, wenn gleiche Elemente danach in derselben Reihenfolge stehen wie vorher. Bei Zahlen allein sieht man davon nichts, bei Datensätzen schon: Wer eine nach Namen sortierte Liste stabil nach Noten sortiert, hat bei gleicher Note die Namen noch alphabetisch. In den Beispielen ab Insertion Sort tragen gleiche Zahlen deshalb einen Buchstaben, 3a, 3b, 3c, in ihrer Reihenfolge vom Anfang, und am Ende steht da, ob sie die behalten haben.
Suche die kleinste Zahl und tausche sie an Index 0. Suche unter den übrigen die kleinste und tausche sie an Index 1. Und so weiter. Invariante: Links von Index i stehen die i kleinsten Zahlen, sortiert.
selection_sort(list): for i from 0 to length - 2: min ← i for j from i + 1 to length - 1: if list[j] < list[min]: min ← j swap list[i] and list[min]
Selection Sort braucht immer gleich viele Vergleiche, \(\frac{n(n-1)}{2}\), ob die Liste schon sortiert ist oder nicht: Bei 8 Zahlen 28, bei 100 schon 4 950. Dafür tauscht es höchstens \(n - 1\)-mal, das wenigste von allen.
So sortiert man Spielkarten in der Hand: Nimm die nächste Karte und schieb sie nach links, an allen größeren vorbei, bis sie passt. Invariante: Links von Index i ist alles sortiert, aber noch nicht unbedingt an seinem endgültigen Platz.
insertion_sort(list): for i from 1 to length - 1: current ← list[i] j ← i while j > 0 and list[j - 1] > current: list[j] ← list[j - 1] (eins nach rechts rücken) j ← j - 1 list[j] ← current
Das angehobene Element ist das, das gerade einsortiert wird:
Ist die Liste schon sortiert, braucht Insertion Sort nur \(n - 1\) Vergleiche, ist sie umgekehrt sortiert, \(\frac{n(n-1)}{2}\). Für fast sortierte Listen ist es deshalb sehr gut, und für kurze Listen auch: Viele schnelle Verfahren sortieren die kleinen Stücke am Ende mit Insertion Sort.
Typische Fehler: j bis unter 0 laufen lassen (erst j > 0 prüfen, dann list[j - 1] lesen); current erst nach dem Verschieben aus der Liste lesen, dann ist es schon überschrieben.
Geh durch die Liste und vertausche zwei Nachbarn, wenn der linke größer ist. Nach einem Durchgang ist die größte Zahl ganz rechts angekommen, wie eine Blase, die aufsteigt. Der nächste Durchgang muss sie nicht mehr ansehen. Invariante: Rechts von end stehen die größten, an ihrem Platz.
bubble_sort(list): for end from length - 1 down to 1: swapped ← false for i from 0 to end - 1: if list[i] > list[i + 1]: swap list[i] and list[i + 1] swapped ← true if not swapped: done
Bubble Sort ist leicht zu verstehen und leicht richtig zu schreiben, aber langsam: Es tauscht viel öfter als die anderen. swapped sorgt dafür, dass es bei einer sortierten Liste nach einem Durchgang aufhört.
Teile die Liste in zwei Hälften, sortiere jede Hälfte (mit Merge Sort, also rekursiv), und führe die beiden sortierten Hälften zusammen. Zum Zusammenführen schaut man nur auf die vordersten beiden Zahlen der Hälften und nimmt die kleinere. Eine Liste mit einer Zahl ist schon sortiert, dort hört die Rekursion auf.
merge_sort(list, start, stop): (stop gehört nicht mehr dazu) if stop - start < 2: done middle ← (start + stop) / 2, rounded down merge_sort(list, start, middle) merge_sort(list, middle, stop) i ← start, j ← middle for k from start to stop - 1: if i < middle and (j ≥ stop or list[i] ≤ list[j]): scratch[k] ← list[i], i ← i + 1 else: scratch[k] ← list[j], j ← j + 1 copy scratch[start … stop - 1] back to list
Unter den Balken steht der Zwischenspeicher; die gestrichelte Linie trennt die beiden Hälften, die gerade zusammengeführt werden:
Merge Sort braucht immer etwa \(n \log_2 n\) Vergleiche, auch im schlechtesten Fall, und lässt gleiche Zahlen in ihrer Reihenfolge (es ist stabil). Dafür braucht es einen Zwischenspeicher so groß wie die Liste; in der Sandbox ist das scratch.
Typische Fehler: ≤ statt < beim Zusammenführen vergessen (dann ist es nicht mehr stabil); eine Hälfte ist leer, und man liest trotzdem list[j] hinter dem Ende.
John von Neumann (1903–1957), Mathematiker aus Budapest, ab 1930 in den USA. Merge Sort dachte er sich 1945 aus; den Teil, der zwei sortierte Folgen zusammenfügt, schrieb er als eines der ersten Programme für einen Rechner auf, der sein Programm im Speicher hält.
Wie ein solcher Rechner gebaut ist, beschrieb er im selben Jahr: Programm und Daten im selben Speicher. So sind Computer bis heute gebaut, auch die MiniCPU der CPU Sandbox.
Foto: Los Alamos National Laboratory, 1940er Jahre, frei mit Namensnennung, zugeschnitten (Wikimedia Commons)
Wähle eine Zahl, das Pivot, hier die letzte des Bereichs. Bringe alle kleineren nach links und alle anderen nach rechts, und setze das Pivot dazwischen: Jetzt steht es an seinem endgültigen Platz. Sortiere dann links und rechts davon auf dieselbe Weise.
quick_sort(list, first, last): (last gehört dazu) if last ≤ first: done pivot ← list[last] boundary ← first for i from first to last - 1: if list[i] < pivot: swap list[i] and list[boundary] boundary ← boundary + 1 swap list[boundary] and list[last] (das Pivot an seinen Platz) quick_sort(list, first, boundary - 1) quick_sort(list, boundary + 1, last)
Rot ist das Pivot, die rote gestrichelte Linie die Grenze: Links von ihr stehen die Zahlen, die kleiner sind als das Pivot.
Quick Sort ist in der Praxis meist das schnellste der fünf: Es braucht keinen Zwischenspeicher, und bei zufälligen Zahlen teilt das Pivot den Bereich ungefähr in der Mitte, das gibt etwa \(n \log_2 n\) Vergleiche. Ist die Liste aber schon sortiert, ist das letzte Element immer das größte, die eine Seite bleibt leer, und es werden \(\frac{n(n-1)}{2}\). Darum wählt man das Pivot in der Praxis zufällig oder nimmt den mittleren von drei Werten.
Tony Hoare (1934–2026), britischer Informatiker. Quick Sort erfand er 1959 als Austauschstudent in Moskau: Er sollte ein Programm schreiben, das Russisch übersetzt, und musste dafür die Wörter eines Satzes sortieren.
1965 baute er in eine Programmiersprache den Wert null ein, »weil es so einfach war«. Später nannte er ihn seinen »Milliarden-Dollar-Fehler«: Meldungen wie undefined method … for nil in Ruby stammen von dieser Idee.
Foto: Rama, 2011, CC BY-SA 2.0 fr, zugeschnitten (Wikimedia Commons)
Quicksort, C. A. R. Hoare, The Computer Journal, 1962. Hoare beschreibt sein Verfahren ausführlich und untersucht, wie schnell es ist; 1961 hatte er es schon als kurzes Programm in den Communications of the ACM gedruckt. Er teilt anders als der Pseudocode oben: Zwei Zeiger laufen von beiden Enden aufeinander zu und tauschen, was auf der falschen Seite steht. Die Fassung oben, mit dem letzten Element als Pivot, geht auf Nico Lomuto zurück. Der Aufsatz steht frei bei Oxford University Press.
Die Zahl der Vergleiche für 100 Zahlen, gezählt mit genau den Verfahren oben:
| Verfahren | zufällig | schon sortiert | umgekehrt sortiert | wächst mit |
|---|---|---|---|---|
| Selection Sort | 4 950 | 4 950 | 4 950 | \(n^2\) |
| Insertion Sort | 2 374 | 99 | 4 950 | \(n^2\), sortiert \(n\) |
| Bubble Sort | 4 779 | 99 | 4 950 | \(n^2\), sortiert \(n\) |
| Merge Sort | 542 | 316 | 356 | \(n \log n\) |
| Quick Sort (letztes als Pivot) | 584 | 4 950 | 4 950 | \(n \log n\), schlimmstenfalls \(n^2\) |
| Heapsort | etwa \(2 n \log_2 n\), in jedem Fall | \(n \log n\) | ||
Bei 100 Zahlen ist der Unterschied zwischen 550 und 5 000 Vergleichen noch klein. Bei einer Million Zahlen sind es etwa 20 Millionen gegen 500 Milliarden: Sekunden gegen Tage. Schneller als \(n \log_2 n\) Vergleiche geht es übrigens nicht, wenn man nur vergleichen darf. Wer mehr über die Zahlen weiß, etwa dass es nur ganze Zahlen von 0 bis 100 sind, kann sie auch zählen statt vergleichen und ist dann noch schneller.
Im eigenen Programm sortierst du mit dem, was die Sprache mitbringt: sort und sort_by in Ruby, sorted und list.sort in Python. Die Verfahren auf dieser Seite programmierst du selbst, um zu verstehen, wie Sortieren geht und was es kostet.
Array#sort und sort_by: sortieren mit <=> oder nach einem Schlüssel. Rubys Sortieren ist nicht garantiert stabil: Gleiche Werte können ihre Reihenfolge tauschen.sorted und list.sort, Sortieren nach einem Schlüssel (key=) und absteigend, und warum Pythons Sortieren stabil ist. Python sortiert mit Timsort, einer Mischung aus Merge Sort und Insertion Sort.