Der Begriff Blasensortierung oder oft englisch Bubblesort bezeichnet einen einfachen, stabilen Sortieralgorithmus, der eine Reihe linear angeordneter Elemente (etwa Zahlen) der Größe nach anordnet.
Bubblesort wird von Donald E. Knuth als vergleichsbasierter Sortieralgorithmus bezeichnet [1]. Das bedeutet, dass der Sortieralgorithmus sämtliche Entscheidungen alleine auf Basis des Größenvergleichs je zweier Elemente fällt, nicht etwa aufgrund der Inspektion der Binärdarstellung eines Elements. Bubblesort ist der einfachste solche Algorithmus. Einzige Anforderung an den Vergleichsoperator ist, dass er eine Totalordnung der Liste ermöglicht.
Bubblesort gehört zur Klasse der In-place-Verfahren, was bedeutet, dass der Algorithmus zum Sortieren keinen zusätzlichen Arbeitsspeicher außer den lokalen Laufvariablen der Prozedur benötigt.
Wegen der einerseits mangelhaften Effizienz und anderseits breiten Verfügbarkeit deutlich besserer Alternativen wird Bubblesort meistens nur als Beispiel für einen schlechten oder naiven Sortieralgorithmus verwendet.
Prinzip
Der Algorithmus vergleicht der Reihe nach zwei benachbarte Elemente und vertauscht sie, falls sie in der falschen Reihenfolge vorliegen. Dieser Vorgang wird solange wiederholt, bis keine Vertauschungen mehr nötig sind. Hierzu sind in der Regel mehrere Durchläufe erforderlich.
Je nachdem, ob auf- oder absteigend sortiert wird, steigen die größeren oder kleineren Elemente wie Blasen im Wasser (daher der Name) immer weiter nach oben, das heißt, an das Ende der Reihe. Auch werden immer zwei Zahlen miteinander in „Bubbles“ vertauscht.
Analyse
Schlimmster Fall
Bubblesort hat die schlechtestmögliche Laufzeit Θ(n2) für Listen der Länge n. Das liegt daran, dass kein Element je mehr bewegt wird als einen Schritt pro Durchlauf. Kein Element kann mehr als Stellen entfernt von der endgültig sortierten Position entfernt sein, darum benötigt man höchstens n-1 = Θ(n) viele Schritte um ein Element an seinen endgültigen Platz zu verschieben und schlimmstenfalls (n - 1)2 = Θ(n2) Schritte für die gesamte Liste.
Falls das kleinste Element der Liste ganz unten steht wird jeder Durchlauf es nur um einen Schritt bewegen und so benötigt man wieder n-1 Durchläufe um es an seine endgültige Position zu bewegen. Da jeder Durchlauf die ganze Liste prüfen muss sind für jeden einzelnen Durchlauf n-1 Operationen nötig. Daher ist die Komplexität im schlimmsten Fall gerade Θ(n2).
Bester Fall
Falls die Liste bereits sortiert ist wird Bubblesort die Liste nur einmal durchgehen um festzustellen, dass die Liste bereits sortiert ist, weil keine benachbarten Elemente vertauscht werden mussten. Daher benötigt Bubblesort Θ(n) Schritte um eine bereits sortierte Liste zu bearbeiten.
Falls die Elemente der Liste bereits nah den Stellen sind, die sie nach der Sortierung bekommen sollen, ist die Laufzeit erheblich besser als Θ(n2).
Durchschnittlicher Fall
Die erwartete Laufzeit für den Algorithmus beträgt Θ(n2/2)[2]
Hasen und Schildkröten
Die Positionen der Elemente vor dem Sortieren entscheiden maßgeblich den Sortieraufwand. Große Elemente am Anfang wirken sich nicht gravierend aus, da sie schnell nach unten getauscht werden, kleine Elemente am Ende bewegen sich jedoch eher langsam nach oben. Darum spricht man bei diesen Elementen von Hasen und Schildkröten.
Verschiedene Anstrengungen wurden unternommen um die Geschwindigkeit der Schildkröten zu verbessern. Ein Algorithmus, der sie erheblich verbessert ist Cocktailsort, der allerdings im schlimmsten Fall immer noch Θ(n2) Schritte benötigt. Combsort vergleicht Elemente die weit von einander entfernt sind und kann Schildkröten darum schnell bewegen bevor die kleineren Sortierungen vorgenommen werden. Dessen Komplexität ist mit schnelleren Algorithmen wie Quicksort vergleichbar.
Beispiel
Eine Reihe von fünf Zahlen soll aufsteigend sortiert werden.
Die fett gedruckten Zahlen werden jeweils verglichen. Ist die linke größer als die rechte, so werden beide vertauscht; das Zahlenpaar ist dann blau markiert. Im ersten Durchlauf wandert somit die größte Zahl ganz nach rechts. Der zweite Durchlauf braucht somit die letzte und vorletzte Position nicht mehr zu vergleichen. --> Dritter Durchlauf: kein Vergleich letzte/vorletzte/vorvorletzte....
55 07 78 12 42 1. Durchlauf 07 55 78 12 42 07 55 78 12 42 07 55 12 78 42 07 55 12 42 78 2. Durchlauf 07 55 12 42 78 07 12 55 42 78 07 12 42 55 78 3. Durchlauf 07 12 42 55 78 07 12 42 55 78 4. Durchlauf 07 12 42 55 78 Fertig sortiert.
Formaler Algorithmus
Der Algorithmus sieht im Pseudocode so aus:
prozedur bubbleSort( A : Liste sortierbarer Elemente ) definiert als:
n := Länge( A ) - 1
wiederhole
vertauscht := falsch
für jedes i in 0 bis n wiederhole:
falls A[ i ] > A[ i + 1 ] dann
vertausche( A[ i ], A[ i + 1 ] )
vertauscht := true
falls ende
für ende
n := n - 1
während vertauscht
prozedur ende
Quellen
- ↑ D. E. Knuth. The Art of Computer Programming. Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 5.3.1: Minimum-Comparison Sorting, pp.180–197
- ↑ Laufzeitbetrachtung (englisch)
Siehe auch
Weblinks
- VisuSort Framework - Visualisierung diverser Sortieralgorithmen (Windows)
- Visualisierung von BubbleSort
- Java-Applet und Code zur Visualisierung
- http://olli.informatik.uni-oldenburg.de/fpsort/Animation.html - interaktive Animation des Verfahrens mit Codebeispielen
- http://www.inf.ethz.ch/~staerk/algorithms/SortAnimation.html - Java-Beispiele für Sortieralgorithmen
- http://en.wikibooks.org/wiki/Algorithm_implementation/Sorting/Bubble_sort