20.05.2012
Liste von weiteren Sortierverfahren
Englische Version

Bubble Sort

BubbleSort ist ein sehr einfacher vergleichsbasierter Sortieralgorithmus. Den Namen verdankt er der Weise wie die Elemente nach und nach wie Blasen im Wasser nach hinten (bzw. vorne) wandern. BubbleSort ist sehr simpel zu verstehen und wird meist als einführender Sortieralgorithmus vorgestellt, ist aber auch meist sehr ineffizient (besonders bei großen Datenmengen).

  • sehr einfach zu verstehen und zu implementieren
  • stabil (die Reihenfolge von schon sortierten Elementen ändert sich nach Sortierung nicht)
  • in-place (bzw. in-situ, d.h. es wird kein zusätzlicher Speicher benötigt)

Idee

Der Algorithmus durchläuft die zu sortierende Folge und vertauscht benachbarte Paare, die in der falschen Reihenfolge vorliegen. Dies garantiert das die großen Elemente nach und nach ans Ende der Folge wandern. Dieser Durchlauf wird solange wiederholt bis keine Vertauschungen mehr nötig sind und die Folge damit sortiert ist. Um die Geschwindigkeit zu verbessern bedarf es nur den Durchlauf bis zu den schon nach hinten gewanderten Elementen, da diese bereits an die richtige sortierte Position gewandert sind. Dadurch wird stets ein Element weniger geprüft, ändert aber insgesamt nichts an der Komplexität des Algorithmus.

Applet

© Miao Wang 2006 (Bug-Meldungen bitte an Webmaster@Wanginator.de richten)

Das Applet (benötigt Java) visualisiert einen BubbleSort auf maximal 16 Elemente. Jede Iteration durchläuft die Liste und vertauscht Elemente, die in der falschen Reihenfolge vorliegen. Nach hinten gewanderte Elemente werden nicht mehr überprüft und durch eine Linie getrennt. Es werden alle Durchläufe visualisiert, ein vorzeitiger Abbruch findet nicht statt. Mit Insert lassen sich Werte zur Folge hinzufügen, mit Random Fill erhält man eine zufällige volle Folge generiert und mit Clear löscht man die aktuelle Folge. Mit einem Klick auf Sort wird stets ein Schritt des Verfahrens visualisiert.

Quellcode (Java)

Java Code:
Syntax Highlightning by Beautifier
public class BubbleSort { public static void bubblesort (int[] a){ //äußere For-Schleife (so viele Durchläufe wie Elemente) for(int i=1; i<a.length; i++) { //innere For-Schleife (läuft bis schon platzierten Elementen) for(int j=0; j<a.length-i; j++) { //falls in falscher Reihenfolge, dann vertauschen if (a[j]>a[j+1]) swap(a, j, j+1); } } } //vertauscht zwei Elemente im Array private static void swap (int[] a, int i, int j) { int h = a[i]; a[i] = a[j]; a[j] = h; } }

Varianten

BubbleSort kann modifiziert werden, indem man die Richtung in der die Elemente durchlaufen werden in jeder Iteration ändert. Die Elemente werden so abwechselnd von vorne nach hinten und von hinten nach vorne durchlaufen. Diese Modifikation nennt sich ShakeSort (oder CocktailSort). Dies mag in der Praxis manchmal Vorteile bringen, ist aber theoretisch nicht schneller als der normale BubbleSort.

Analyse

Die Komplexität von BubbleSort ist stark abhängig inwieweit die Elemente von ihrer richtigen sortierten Position entfernt sind. Im Best Case ist die Folge bereits sortiert und der Algorithmus benötigt einen Durchlauf und bricht danach ab, was eine Laufzeit von O(n) verursacht. Im Worst Case beträgt die Laufzeit jedoch O(n2), wie man schön an der verschachtelten For-Schleife sehen kann. Es kann auch berechnet werden, indem man sich überlegt, dass ein Element nie mehr als n Positionen von der sortierten Position entfernt sein kann und sich nur um eine Position pro Iteration bewegt.

Obwohl BubbleSort im Worst Case asymptotisch gleich schnell wie InsertionSort ist, unterscheiden sich die Anzahl der Vertauschungen in beiden Verfahren enorm. In der Praxis zeigt sich das BubbleSort viel langsamer läuft und sich als extrem ineffizient präsentiert.

Weiterführende Links und Literatur

Last Update: 05.04.2011 02:46:53
Valid XHTML 1.0 Transitional!Valid CSS!