Bubblesort

Bubblesort ist ein einfacher, stabiler Sortieralgorithmus, der eine Reihe von linear angeordneten Elementen (z.B. Zahlen) der Größe nach anordnet.

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 kleineren oder größeren Elemente wie Blasen im Wasser (daher der Name) immer weiter nach oben, d.h. an das Ende der Reihe.

Komplexität

Der Algorithmus besitzt eine quadratische und daher im Vergleich zu vielen anderen Sortieralgorithmen schlechte Worst-Case-Laufzeit, in der Informatik drückt man dies mittels Landau-Symbol durch O(n²) aus. Jedoch bietet dieser Algorithmus folgende Vorteile:

• geringer Speicherbedarf, da dieser Algorithmus einin-place Verfahren ist und anders als z.B. Quicksort keinen zusätzlichen Speicher beim Aufruf-Stack belegt
• bereits vorsortierte Daten werden schnell verarbeitet, zum Beispiel wird der Algorithmus bei einem vollständig sortierten Datensatz nach einem Schleifendurchlauf abgebrochen

Beispiel

Eine Reihe von 5 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.

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

Im folgenden sei die zu sortierende Datenreihe mit x bezeichnet. Sie enthält N Elemente, die von 1 bis N indiziert seien, d.h. x[1], ..., x[N]. Es ist wichtig, die Schleifengrenzen korrekt zu wählen.

Schleife über Durchlauf = 1 .. N
{
  Schleife über Position = 1 .. N-Durchlauf
  {
    Falls x[Position] > x[Position+1] ...
    {
      ... dann Vertausche x[Position] und x[Position+1]
    }
  }
}

Varianten

Die Geschwindigkeit kann erhöht werden, indem man eine Abbruchbedingung einbaut, die die äußere Schleife beendet, falls bei einem Durchlauf der inneren Schleife keine Vertauschung stattgefunden hat, die Reihe also bereits sortiert ist. Diese Bubblesort-Variante ist für vorsortierte Arrays ziemlich schnell (d.h. auch schneller als einige andere Algorithmen). Die Aufwandsklasse bleibt allerdings weiterhin O(n²).

Manchmal wird der Bubblesort-Algorithmus modifiziert, indem die Richtung des Schleifendurchlaufs bei jeder Iteration geändert wird. Zunächst wird also von unten nach oben, danach von oben nach unten usw. gesucht, in der Hoffnung, dass die Bubbles dann schneller ihre Position erreichen. Der Algorithmus wird dann auch Shakersort oder Cocktailsort genannt. Die Hoffnung trügt allerdings, der neue Algorithmus ist in keiner Hinsicht besser als Bubblesort, er ist nur etwas komplizierter.

Weblinks

• 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.wikisource.org/wiki/Bubble_sort

Siehe auch: Liste von Algorithmen hallo