Wikipedia · einfach zusammengefasst · Stand
Bubblesort
Bubblesort (auch Sortieren durch Aufsteigen oder Austauschsortieren) ist ein Algorithmus, der vergleichsbasiert eine Liste von Elementen sortiert.
Inhalt6 Abschnitte
Grundidee und Bedeutung
Bubblesort, auch Sortieren durch Aufsteigen oder Austauschsortieren, ist ein vergleichsbasierter Sortieralgorithmus für eine Liste von Elementen. Vergleichsbasiert bedeutet: Die Reihenfolge wird durch Vergleiche zwischen Elementen bestimmt. Bei Bubblesort wird immer ein Element mit seinem rechten Nachbarn verglichen. Ist bei aufsteigender Sortierung das linke Element größer als das rechte, werden beide vertauscht. Dadurch wandern große Elemente Schritt für Schritt nach rechts, ähnlich wie Blasen im Wasser nach oben steigen.
Der Algorithmus arbeitet in-place, das heißt, er sortiert innerhalb der vorhandenen Liste und benötigt keinen zusätzlichen großen Speicherbereich. Er ist außerdem stabil: Gleiche Elemente behalten ihre relative Reihenfolge. Seine Laufzeit beträgt im schlimmsten Fall und im durchschnittlichen Fall Θ(n²). Damit ist Bubblesort asymptotisch nicht optimal und wird in der Praxis kaum verwendet, weil andere Sortierverfahren ein besseres Laufzeitverhalten haben. Wichtig ist Bubblesort vor allem in der Lehre, weil er einfach zu erklären und zu demonstrieren ist und sich gut eignet, um Optimierungen, Laufzeit-, Komplexitäts- und Korrektheitsanalyse einzuführen.
Prinzip des Sortierens
Bubblesort arbeitet in wiederholten sogenannten Bubble-Phasen. In einer Bubble-Phase wird die Liste von links nach rechts durchlaufen. In jedem Schritt wird das aktuelle Element mit seinem rechten Nachbarn verglichen. Verletzen die beiden Elemente das Sortierkriterium, werden sie getauscht. Bei aufsteigender Sortierung steht nach einer solchen Phase das größte Element am Ende der Liste; bei absteigender Sortierung steht dort entsprechend das kleinste Element.
Diese Phase wird so lange wiederholt, bis die Eingabeliste vollständig sortiert ist. Nach jedem Durchlauf muss das letzte Element des vorherigen Durchlaufs nicht mehr betrachtet werden, weil dort bereits das größte beziehungsweise kleinste Element des noch unsortierten Teils steht. Je nach Sortierrichtung steigen größere oder kleinere Elemente immer weiter an das Ende der Liste. Es werden dabei stets benachbarte Elemente paarweise vertauscht.
Algorithmus und Optimierung
Für die Darstellung wird im Artikel die Vergleichsrelation > verwendet, also „größer als“. Wie bei anderen vergleichsbasierten Sortierverfahren kann sie durch eine andere Relation ersetzt werden, sofern diese eine totale Ordnung definiert. Eine totale Ordnung bedeutet, dass die Elemente eindeutig miteinander vergleichbar und sortierbar sind.
In der einfachsten Form liegt die Eingabe in einem Array A. Eine äußere Schleife setzt die rechte Grenze des noch unsortierten Bereichs immer weiter nach links. Eine innere Schleife läuft durch diesen Bereich. Wenn A[i] > A[i + 1] gilt, werden die beiden benachbarten Elemente mit A.swap(i, i + 1) vertauscht. Nach jedem vollständigen Durchlauf steht am rechten Rand des betrachteten Bereichs das größte Element dieses Restbereichs.
Eine optimierte Variante nutzt die Beobachtung, dass nach einem Durchlauf ohne Vertauschung die Liste bereits sortiert ist. Dazu verwendet sie eine Variable swapped. Vor einem Durchlauf wird swapped auf false gesetzt. Findet ein Tausch statt, wird swapped auf true gesetzt. Die äußere Schleife läuft nur weiter, solange in einem Durchlauf mindestens eine Vertauschung nötig war. Dadurch kann Bubblesort bei bereits sortierten oder fast sortierten Listen deutlich früher abbrechen.
Beispielablauf
Im Beispiel soll die Zahlenfolge 55 07 78 12 42 aufsteigend sortiert werden. In jedem Schritt werden zwei benachbarte Zahlen verglichen. Ist die linke Zahl größer als die rechte, werden beide vertauscht.
Im ersten Durchlauf wandert die größte Zahl 78 nach rechts. Aus 55 07 78 12 42 wird zunächst 07 55 78 12 42. Später wird 78 mit 12 und danach mit 42 verglichen und jeweils vertauscht, sodass am Ende des ersten Durchlaufs 07 55 12 42 78 steht. Die 78 ist damit bereits an ihrer endgültigen Position.
Im zweiten Durchlauf muss die letzte Position nicht mehr betrachtet werden. Die Folge wird weiter sortiert: 07 55 12 42 78 wird zu 07 12 55 42 78 und danach zu 07 12 42 55 78. Im dritten und vierten Durchlauf sind keine weiteren wirksamen Änderungen mehr nötig. Am Ende ist die Liste vollständig sortiert: 07 12 42 55 78.
Laufzeit und Fälle
Für Listen der Länge n hat Bubblesort im ungünstigsten Fall die Laufzeit O(n²). Dieser Fall tritt zum Beispiel bei der umgekehrt sortierten Liste (n, n−1, …, 2, 1) auf. Dann werden maximal n·(n−1)/2 Vertauschungen ausgeführt. Um das erste und größte Element n ganz nach rechts zu bewegen, sind n−1 Vertauschungen nötig. Allgemein braucht die Bewegung des k-ten Elements an die Stelle n genau n−k Vertauschungen. Aufsummiert ergibt das 1/2·(n²−n) ∈ O(n²). Da nur Paare vertauscht werden, die vorher verglichen wurden, benötigt der Algorithmus mindestens ebenso viele Vergleiche.
Im besten Fall ist die Liste bereits sortiert. Dann genügt ein einziger Durchgang, um festzustellen, dass keine benachbarten Elemente vertauscht werden müssen. In diesem Fall benötigt Bubblesort O(n) Schritte. Sind die Elemente bereits nahe an den Positionen, die sie nach dem Sortieren bekommen sollen, kann die Laufzeit ebenfalls deutlich besser sein als O(n²).
Im durchschnittlichen Fall betrachtet der Artikel eine zufällig gewählte Permutation der Liste (1,2,…,n). Die erwartete Anzahl der Vergleiche ist 1/2·(n² − n·ln n − (γ + ln(2) − 1)·n) + O(√n), wobei γ die Euler-Mascheroni-Konstante bezeichnet. Die erwartete Anzahl der Vertauschungen beträgt 1/4·(n²−n).
Einordnung und Varianten
Obwohl Bubblesort asymptotisch nicht optimal ist, kann er bei kleinen Eingaben in Frage kommen, weil dort konstante Laufzeitfaktoren stark ins Gewicht fallen und diese bei Bubblesort klein sind. Ein möglicher Einsatz wäre innerhalb eines rekursiven Sortierverfahrens, um die Anzahl der Rekursionen zu verringern. Außerdem eignet sich Bubblesort, wenn Elemente eines Feldes oder einer Liste mit hoher Wahrscheinlichkeit bereits sortiert sind, denn dann tritt der Best-Case mit linearer Laufzeit ein. Andere effiziente Verfahren wie Quicksort oder asymptotisch optimale Verfahren wie Mergesort haben im Best-Case O(n log n).
Unter diesem Gesichtspunkt konkurriert Bubblesort mit Insertionsort. Auch Insertionsort hat als Best-Case eine schon sortierte Folge und weist im Best-, Average- und Worst-Case die gleiche Komplexität wie Bubblesort auf. Beide Verfahren sind stabil und arbeiten in-place. Je nach Implementation hat Insertionsort jedoch geringere konstante Laufzeitfaktoren.
Die Ausgangsposition der Elemente ist für Bubblesort wichtig. Große Elemente am Anfang sind unproblematisch, weil sie schnell nach hinten wandern. Kleine Elemente am Ende bewegen sich dagegen nur langsam nach vorn. Schnell wandernde Elemente werden deshalb als Hasen bezeichnet, langsam wandernde als Schildkröten.
Combsort, auch Gapsort genannt, beruht auf Bubblesort, vergleicht und vertauscht aber weiter voneinander entfernte Elemente, um langsam wandernde Elemente zu vermeiden. Seine Laufzeit liegt im Worst-Case ebenfalls bei O(n²), im Best-Case bei O(n log √n). Cocktailsort oder Shakersort lässt Elemente abwechselnd von links nach rechts und von rechts nach links wandern und wird deshalb auch Bidirectional-Bubblesort genannt. Sein Worst-Case liegt wie bei Bubblesort in O(n²). Oyelami O.M. veröffentlichte 2009 eine optimierte Version, die den Worst-Case für umgekehrt sortierte Felder oder Listen vermeidet; wegen der Sortierung über Distanz ist dieser Algorithmus nicht mehr stabil.
