Bubblesort

Bubblesort ist ein primitiver Sortieralgorithmus, der nebeneinander liegende Elemente vergleicht und ggf. vertauscht, falls sie in der falschen Reihenfolge vorliegen. 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 den Anfang des zu sortierenden Arrays.

Der Algorithmus besitzt eine quadratische und daher im Vergleich zu anderen Sortieralgorithmen eher schlechte Worst-Case-Laufzeit, Informatiker notieren dies mittels Landau-Symbol durch O(n²). Trotz der theoretisch schlechten Laufzeit findet er Anwendung in der Abbruchbedingung rekursiver Sortieralgorithmen wie QuickSort oder MergeSort, da er für eine sehr kleine Anzahl an zu sortierenden Elementen schneller ist als fortgesetzte rekursive Funktionsaufrufe.

Beispiel für aufsteigende Sortierung:

Die blau eingefärbten Zahlen werden jeweils verglichen und vertauscht, wenn die linke größer ist als die rechte.

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.

siehe auch: Liste von Algorithmen