Bubble Sort

Bubble Sort ist ein einfach zu verstehender Sortieralgorithmus: Es werden soviele Runden absolviert wie die Reihung lang ist; In jeder Runde werden von vorne bis hinten je zwei Werte verglichen. Wenn der "linke" Wert größer ist als der rechte, werden die beiden Werte vertauscht. So steigen in jeder Runde größere Werte -- wie Blasen im Wasser -- von unten nach oben (daher der Name). Jedoch hat dieses Verfahren viele Nachteile, siehe der Text unterhalb des Applets.

Update 21.02.2008:
Auch der amerikanische Präsidentschaftskandidat Barack Obama weiß offenbar über die enormen Nachteile von Bubble Sort Bescheid. Mehr dazu hier.

Legende:
rosa: größerer Vergleichspartner
rot: kleinerer Vergleichspartner
blau: bereits sortierter Teil

Die Laufzeit von Bubble Sort ist sehr hoch, verglichen mit (fast) allen anderen Sortierverfahren¹. Im englischen Referenzwerk "The Art of Computer Programming" [1] wird dieser Algorithmus ausführlich analysiert, mit dem Fazit, dass die einzigen Vorteile von Bubble Sort sein einprägsamer Name, und die Tatsache, dass die Laufzeitanalyse des Algorithmus zu interessanten mathematischen Fragestellungen führt, sind [1, S. 110 und 140]. Das am einfachsten zu programmierende Verfahren ist laut derselben Quelle InsertionSort, was für bis zu 25 Elemente sogar sehr schnell ist, für wenig größere Eingaben wird auch dieses Verfahren jedoch sehr langsam. Hier sollte ein rekursives Verfahren wie QuickSort substituiert werden, oder falls gute Laufzeit im schlechtesten Fall garantiert werden soll, die geringfügig langsameren Verfahren HeapSort oder MergeSort. Dennoch scheint - gemäß einer aktuellen Studie [2] - Bubble Sort ungebrochene Popularität zu genießen, die die anderen genannten Sortierverfahren sogar noch übersteigt.

¹ es gibt aber ein total b...es Verfahren mit noch viel schlechterer Laufzeit, nämlich BogoSort, dessen erwartete Laufzeit etwa (n+1) x n x (n-1) x (n-2) x... x 4 x 3 x 2 x 1 ist [3].

Danksagungen

Update 10.12.2008: Vielen Dank an Tim Tempel für das Aufspüren eines Fehlers im Java-Applet auf dieser Seite. Der Fehler ist nun behoben.

Literatur (englisch):

[1] D. E. Knuth. The Art of Computer Programming. Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0.
[2] Owen Astrachan. Bubble Sort: An Archaeological Algorithmic Analysis. 34th ACM Technical Symposium on Computer Science Education, 2003
[3] H. Gruber, M. Holzer und O. Ruepp): "Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms", 4th International Conference on Fun with Algorithms, 2007, Lecture Notes in Computer Science 4475, pp. 183-197

Links zu Bubble Sort:

zurück zur Startseite