Sortieralgorithmen

Bubblesort

Schritt 1 von 70

Tempo

← → Schritt, Leertaste Abspielen

Vorhersagen üben

Die Idee

Große Werte steigen auf

Bubblesort läuft immer wieder von links nach rechts durch das Feld und vergleicht dabei je zwei Nachbarn. Steht der größere links, tauschen die beiden. So wandert in jedem Durchlauf der größte noch unsortierte Wert ganz nach rechts, wie eine Blase im Wasser nach oben.

Idee

Vergleiche immer zwei Nachbarn und tausche sie, wenn der größere links steht. Nach einem Durchlauf ist der größte Wert ganz rechts angekommen, nach dem zweiten der zweitgrößte, und so weiter.

Pseudocoden = 10, Stellen 0 bis 9

für i von 0 bis n − 2:
getauscht ← falsch
für j von 0 bis n − 2 − i:
wenn A[j] > A[j + 1]:
tausche A[j] und A[j + 1]; getauscht ← wahr
A[n − 1 − i] steht jetzt endgültig
wenn nicht getauscht: fertig

Laufzeit

Bester Fall: $\Theta(n)$
Im Mittel: $\Theta(n^2)$
Schlechtester Fall: $\Theta(n^2)$
Stabil: ja; Gleiche Werte behalten ihre Reihenfolge.
Hilfsfeld: nein; Es wird im Feld selbst gearbeitet.

Wie man darauf kommt

Im Durchlauf $i$ (gezählt ab 0) werden $n-1-i$ Nachbarpaare verglichen. Ohne vorzeitigen Abbruch sind das zusammen $(n-1) + (n-2) + \dots + 1 = \frac{n(n-1)}{2}$ Vergleiche.

Jede Vertauschung zweier Nachbarn beseitigt genau einen Fehlstand. Deshalb ist die Zahl der Vertauschungen gleich der Zahl der Fehlstände: im schlechtesten Fall $\frac{n(n-1)}{2}$ , im Mittel die Hälfte davon.

Ist die Eingabe schon sortiert, genügt ein Durchlauf mit $n-1$ Vergleichen und ohne Vertauschung.

Der Reiter „Alle Verfahren im Vergleich“ zeigt: Bubblesort braucht genau so viele Vertauschungen, wie die Eingabe Fehlstände hat.

Mehr zu Bubblesort

Was immer gilt

Nach dem k-ten Durchlauf stehen die k größten Werte in der richtigen Reihenfolge ganz rechts, auf den Stellen $n-k$ bis $n-1$ .

Warum es richtig sortiert

Sobald ein Durchlauf beim größten Wert des unsortierten Teils ankommt, gewinnt dieser jeden weiteren Vergleich und wird bis ans Ende mitgenommen. Nach höchstens $n-1$ Durchläufen steht also alles am Platz. Gibt es in einem Durchlauf keine einzige Vertauschung, steht jedes Nachbarpaar richtig herum; dann ist das ganze Feld sortiert, und man darf aufhören.

Zusatzspeicher

Nur ein paar Hilfsvariablen

Wofür es sich eignet

Zum Lernen: Idee und Korrektheit sind sofort einsichtig.
Fast sortierte, sehr kurze Listen, dank des vorzeitigen Abbruchs.

Typische Fehler

Ohne den Merker „getauscht“ läuft Bubblesort auch über eine sortierte Liste alle $n-1$ Durchläufe.
Kleine Werte ganz hinten wandern pro Durchlauf nur eine Stelle nach vorn („Schildkröten“). Shellsort behebt genau das.

Grundbegriffe

Feld A und Stellen: Die Zahlen stehen in einem Feld A. Die Stellen werden ab 0 gezählt: $A[0]$ ist die erste Zahl, $A[n-1]$ die letzte, wobei $n$ die Anzahl der Zahlen ist. $A[lo..hi]$ meint die Stellen von $lo$ bis $hi$ einschließlich; lo und hi stehen für den unteren und den oberen Rand eines Bereichs.
Schreibweise im Pseudocode: Pseudocode beschreibt ein Verfahren in Worten, die einer Programmiersprache ähneln. $x \leftarrow 5$ heißt: x bekommt den Wert 5. $\lfloor x \rfloor$ ist x abgerundet auf eine ganze Zahl, etwa $\lfloor 3{,}7 \rfloor = 3$ . $a \bmod b$ ist der Rest beim Teilen, etwa $17 \bmod 10 = 7$ .
Vergleich, Vertauschung, Schreibzugriff: Ein Vergleich prüft, welcher von zwei Werten größer ist. Ein Schreibzugriff setzt einen einzelnen Wert in eine Zelle, egal ob im Feld A, in einem Hilfsfeld B, in einem Zählfeld oder in einem Eimer. Bei einer Vertauschung tauschen zwei Stellen ihren Inhalt; das sind zwei Schreibzugriffe. Die Arbeit eines Verfahrens ist hier die Summe aus Vergleichen und Schreibzugriffen. So lassen sich tauschende und zurückschreibende Verfahren gerecht vergleichen.
Fehlstand: Ein Fehlstand (Inversion) ist ein Paar von Stellen $i < j$ mit $A[i] > A[j]$ : Der größere Wert steht vorne. Ein sortiertes Feld hat keinen Fehlstand, ein absteigendes hat alle $\frac{n(n-1)}{2}$ möglichen. Wer nur Nachbarn tauscht, behebt pro Tausch genau einen Fehlstand.
Logarithmus: $\log_2 n$ ist, wie oft man $n$ halbieren kann, bis 1 übrig bleibt: $\log_2 8 = 3$ , weil $8 \to 4 \to 2 \to 1$ . Genauer ist es die Zahl, mit der man 2 potenzieren muss, um $n$ zu erhalten: $2^{\log_2 n} = n$ . Er wächst sehr langsam: $\log_2 1000 \approx 10$ , $\log_2 1\,000\,000 \approx 20$ . Steht hier nur $\log n$ , ist $\log_2 n$ gemeint.
Wachstum: O, Θ und Ω: Man fragt nicht nach der genauen Zahl der Schritte, sondern wie sie wächst, wenn $n$ größer wird. $f(n) = O(g(n))$ heißt: Ab einem gewissen $n$ ist $f(n)$ höchstens ein festes Vielfaches von $g(n)$ , also $f(n) \le c \cdot g(n)$ . $\Omega$ ist dieselbe Aussage nach unten (mindestens), $\Theta$ beides zusammen: $f$ wächst genau wie $g$ . Beispiel: $\frac{n(n-1)}{2} = \Theta(n^2)$ . Doppelt so viele Zahlen heißt dann etwa viermal so viel Arbeit; bei $\Theta(n \log n)$ nur gut doppelt so viel. Die Basis des Logarithmus spielt dabei keine Rolle, weil sich Logarithmen zu verschiedenen Basen nur um einen festen Faktor unterscheiden.
Bester, mittlerer und schlechtester Fall: Dieselbe Anzahl von Zahlen kann je nach Anordnung unterschiedlich viel Arbeit kosten. Der schlechteste Fall ist die teuerste Anordnung, der beste die billigste. Der mittlere Fall ist der Durchschnitt über alle Anordnungen, wenn jede gleich wahrscheinlich ist.
Invariante: Eine Invariante ist eine Aussage, die vor und nach jedem Durchlauf einer Schleife gilt, etwa „die ersten k Stellen sind sortiert“. Gilt sie am Anfang, bleibt sie bei jedem Durchlauf erhalten und folgt aus ihr am Ende „alles ist sortiert“, dann ist das Verfahren korrekt. So beweist man Sortierverfahren.
Rekursion: Ein Verfahren arbeitet rekursiv, wenn es sich selbst für ein kleineres Stück derselben Aufgabe aufruft. Mergesort sortiert ein Feld, indem es beide Hälften sortiert, jede wieder durch Sortieren ihrer Hälften, bis nur noch einzelne Zahlen übrig sind, die schon sortiert sind. Der Aufrufbaum zeigt, welcher Aufruf welche weiteren gestartet hat.
Stabil: Ein Verfahren ist stabil, wenn gleiche Werte ihre ursprüngliche Reihenfolge behalten. Das zählt, wenn Datensätze nach mehreren Merkmalen nacheinander sortiert werden, etwa erst nach Name und dann nach Note: Ein stabiles Verfahren lässt Schüler mit gleicher Note alphabetisch stehen. Im Tool tragen gleiche Werte Kennbuchstaben, und am Ende steht eine Stabilitätsprüfung.
In place: Ein Verfahren arbeitet in place, wenn es außer dem Feld selbst nur wenige einzelne Hilfsvariablen braucht, also zusätzlichen Speicher, der nicht mit $n$ wächst (oder höchstens wie $\log n$ ). Mergesort braucht dagegen ein zweites Feld derselben Größe.
Untere Schranke für vergleichende Verfahren: Kein Verfahren, das nur durch Vergleiche zweier Werte sortiert, kommt im schlechtesten Fall mit weniger als etwa $n \log_2 n$ Vergleichen aus. Die Idee: Es gibt $n!$ mögliche Anordnungen von $n$ verschiedenen Zahlen, und das Verfahren muss jede von jeder anderen unterscheiden. Jeder Vergleich hat nur zwei Ausgänge; nach $h$ Vergleichen lassen sich also höchstens $2^h$ Fälle auseinanderhalten. Aus $2^h \ge n!$ folgt $h \ge \log_2(n!) \approx n \log_2 n - 1{,}44\,n$ . Mergesort und Heapsort erreichen diese Schranke bis auf einen festen Faktor. Countingsort, Radixsort und Bucketsort umgehen sie, weil sie den Wert selbst als Adresse benutzen statt nur zu vergleichen.
Was Programmiersprachen wirklich benutzen: Bibliotheken kombinieren mehrere Verfahren. Timsort (Python, Java für Objekte) sucht bereits sortierte Stücke in der Eingabe, verlängert kurze mit Insertionsort und mischt sie wie Mergesort; es ist stabil und auf fast sortierten Daten sehr schnell. Introsort (verbreitet in C++) beginnt mit Quicksort, wechselt zu Heapsort, wenn die Rekursion zu tief wird, und erledigt kleine Stücke mit Insertionsort; so bleibt der schlechteste Fall bei $n \log n$ . Pdqsort (Go, und Grundlage der instabilen Sortierung in Rust) ist ein Quicksort, der Muster wie sortierte oder viele gleiche Werte erkennt.

Mehr Theorie: Kapitel „Sortieralgorithmen“ im Uni-Bereich.