Das Kefk Network Wiki befindet sich im Testbetrieb.
Bubblesort
Aus Kefk.
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.
Inhaltsverzeichnis |
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 Laufzeit Θ(n2) für Listen der Länge n. Im Falle der umgekehrt sortierten Liste (n,n-1,...,2,1) werden maximal viele Vertauschungen ausgeführt: um das erste (und größte) Element n ganz nach rechts zu bewegen, werden n − 1 Vertauschungen vorgenommen. Allgemein: Die Bewegung des k-ten Elements an die Stelle n − k wird durch n − k Vertauschungen vollzogen. Aufsummieren über alle k ergibt im Ganzen 1 / 2(n2 − n) = Θ(n2) Vertauschungen. Da nur Paare vertauscht werden, die auch vorher verglichen wurden, benötigt der Algorithmus auch mindestens ebenso viele Vergleiche. Betrachtet man den Pseudocode des Algorithmus, so sieht man leicht ein, dass keine der Anweisungen öfter als 1 / 2(n2 − n) mal ausgeführt werden kann, also ist dies auch die bestmögliche untere Schranke.
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 Anzahl der Vergleiche für eine zufällig gewählte Permutation der Liste (1,2,...,n) ist
wobei γ die Euler-Mascheroni-Konstante bezeichnet; die erwartete Anzahl der Vertauschungen beträgt 1 / 4(n2 − n), siehe [2], S. 108ff.
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 := wahr
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
- ↑ Knuth, Donald E.: The Art of Computer Programming, Vol. 3: Sorting and Searching (englisch), 2nd Edition, Addison-Wesley, 1981
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
 | Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Bubblesort, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation. |
