Bubble-Sort ist ein Sortieralgorithmus, der eine Liste von Elementen sortiert, indem er benachbarte Elemente vergleicht und gegebenenfalls vertauscht.
Schrittfolge des Algorithmus
Der Algorithmus beginnt beim ersten Element eines unsortierten Arrays und vergleicht die benachbarten Elemente von links nach rechts. Falls das linke Element größer ist als das rechte werden beide vertauscht. Beim Tauschen wird das zu tauschende Element in der temporären Hilfsvariable t zwischengespeichert. Die größeren Elemente steigen im Array auf wie Blasen (Bubbles).Der Algorithmus durchläuft zwei verschachtelte Schleifen. Die erste For-Schleife mit der Zählvariable i iteriert über die Zeilen des Arrays und läuft bis zum letzten Element (n – 1). Die zweite For-Schleife mit der Zählvariablen j iteriert innerhalb jeder Zeile über die Spalten. Nach n -1 Durchläufen sind alle Elemente im Array sortiert.
******** Pseudocode Bubble-Sort *********
Input: unsorted array A
Output: sorted array A
For i = 1 to n-1 do // Äußere Schleife
For j = 1 to n-i do // Innere Schleife
if A[j-1]> A[j] then
t = A[j]
A[j] = A[j-1]
A[j-1] = t
End if
End For
End For
return A
Komplexität des Algorithmus (Laufzeitanalyse)
Best-Case: O(n2), Worst Case: O(n2), Average Case: O(n2)
Der Bubble-Sort-Algorithmus hat eine konstante Speicherplatzkomplexität O(1). Unabhängig davon, wie viele Elemente die Liste enthält, benötigt er immer eine konstante Menge an zusätzlichem Speicher für die Schleifenvariablen und eine temporäre Hilfsvariable. Seine Laufzeitkomplexität ist aber in allen drei Fällen quadratisch O(n²), da er n-mal die äußere und n-mal die innere Schleife durchläuft (n · n = n²).
Beispiel: Bubble-Sort-Algorithmus im Array A
Der Algorithmus sortiert die sechs Zahlen des Arrays A [ 11, 13, 4, 17, 8, 2 ] in aufsteigender Reihenfolge.
Initialisierung
Array A [ 11, 13, 4, 17, 8, 2 ], Anzahl Elemente n = 6
Zählvariable i = 1
Zählvariable j = 1
Hilfsvariable t = 0
Erster Durchlauf, i = 1, Array A [ 11, 13, 4, 17, 8, 2 ]
Im ersten Durchlauf wird die größte Zahl 17 in fünf Schritten (n – 1) ans Ende des Arrays gebubbelt. Der Algorithmus vergleicht fünfmal das linke Element A [ j – 1] mit dem rechten Element A [ j ] und führt drei Vertauschungen durch.
erster Schritt (j = 1, t = 0)
Array A [11, 13, 4, 17, 8, 2 ]
Vergleich A [ j – 1] = A[0] mit A[ j ] = A[1]: 11 < 13, kein Tausch
zweiter Schritt (j = 2, t = 0)
Array A [11, 13, 4, 17, 8, 2]
Vergleich A [ j – 1] = A[1] mit A[ j ] = A[2]: 13 > 4, 1. Tausch
t = A[ j ] = A[2] = 4
A[ j ] = A[ j – 1] = A[2 – 1] = A[1] = 13 = t
dritter Schritt (j = 3, t = 13)
Array A [11, 4, 13, 17, 8, 2]
Vergleich A [j -1] = A[2] mit A[j] = A[3]: 13 < 17, kein Tausch
vierter Schritt(j = 4, t = 13)
Array A [11, 4, 13, 17, 8, 2]
Vergleich A [j -1] = A[3] mit A[j] = A[4]: 17 > 8, 2. Tausch
t = A[j] = A[4] = 8
A[j] = A[ j – 1] = A[4 – 1] = A[3] = 17 = t
fünfter Schritt (j = 5, t = 17)
Array A [11, 4, 13, 8, 17, 2]
Vergleich A [j -1] = A[4] mit A[j] = A[5]: 17 > 2, 3. Tausch
t = A[j] = A[5] = 2
A[j] = A[j-1] = A[5 – 1] = A[4] = 17 = t
Zweiter Durchlauf, i = 2, Array A [ 11, 4, 13, 8, 2, 17 ]
Im zweiten Durchlauf wird die zweitgrößte Zahl 13 in fünf Schritten (n – 1) nach hinten gebubbelt. Der Algorithmus vergleicht fünfmal das linke Element A [ j – 1] mit dem rechten Element A [ j ] aus und führt drei Vertauschung durch.
erster Schritt (j = 1, t = 17)
Array A [11, 4, 13, 8, 2, 17]
Vergleich A [j-1] = A[0] mit A[j] = A[1]: 11 > 4, 4. Tausch
t = A[j] = A[1] = 11
A[j] = A[j-1] = A[1 – 1] = A[0] = 11 = t
zweiter Schritt (j = 2, t = 11)
Array A [4, 11, 13, 8, 2, 17]
Vergleich A [j -1] = A[1] mit A[j] = A[2]: 11 < 13, kein Tausch
dritter Schritt (j = 3, t = 11)
Array A [4, 11, 13, 8, 2, 17]
Vergleich A [j -1] = A[2] mit A[j] = A[3]: 13 > 8, 5. Tausch
t = A[j] = A[3] = 8
A[j] = A[j-1] = A[3 – 1] = A[2] = 13 = t
vierter Schritt (j = 4, t = 13)
Array A [4, 11, 8, 13, 2, 17]
Vergleich A [j -1] = A[3] mit A[j] = A[4]: 13 > 2, 6. Tausch
t = A[j] = A[4] = 2
A[j] = A[j-1] = A[4 – 1] = A[3] = 13 = t
fünfter Schritt (j = 5, t = 13)
Array A [4, 11, 8, 2, 13, 17]
Vergleich A [j -1] = A[4] mit A[j] = A[5]: 13 < 17, kein Tausch
Dritter Durchlauf, i = 3, Array A [ 4, 11, 8, 2, 13, 17 ]
Im dritten Durchlauf wird die drittgrößte Zahl 11 in fünf Schritten (n – 1) nach hinten gebubbelt. Der Algorithmus führt fünf Vergleiche zwischen linkem A [ j – 1] und rechtem Element A [ j ] ) sowie zwei Vertauschungen durch.
erster Schritt ( j = 1, t = 13)
Array A [4, 11, 8, 2, 13, 17]
Vergleich A [ j – 1] = A[0] mit A[ j ] = A[1]: 4 < 11, kein Tausch
zweiter Schritt (j = 2, t = 13)
Array A [4, 11, 8, 2, 13, 17]
Vergleich A [ j – 1] = A[1] mit A[ j ] = A[2]: 11 > 8, 7. Tausch
t = A[ j ] = A[2] = 8
A[ j ] = A[ j – 1] = A[2 – 1] = A[1] = 11 = t
dritter Schritt ( j = 3, t = 11)
Array A [4, 8, 11, 2, 13, 17]
Vergleich A [ j – 1] = A[2] mit A[ j ] = A[3]: 11 > 2, 8. Tausch
t = A[ j ] = A[3] = 2
A[ j ] = A[ j – 1] = A[3 – 1] = A[2] = 11 = t
vierter Schritt (j = 4, t = 11)
Array A [4, 8, 11, 2, 13, 17]
Vergleich A [ j – 1] = A[3] mit A[ j ] = A[4]: 2 < 13, kein Tausch
fünfter Schritt (j = 5, t = 11)
Array A [4, 8, 2, 11, 13, 17]
Vergleich A [ j – 1] = A[4] mit A[ j ] = A[5]: 13 < 17, kein Tausch
Vierter Durchlauf, i = 4, Array A [ 4, 8, 2, 11, 13, 17 ]
Im vierten Durchlauf wird die viertgrößte Zahl 8 in fünf Schritten (n – 1) nach hinten gebubbelt. Der Algorithmus führt wieder fünf Vergleiche und zwei Vertauschungen durch.
erster Schritt ( j = 1, t = 13)
Array A [4, 8, 2, 11, 13, 17]
Vergleich A [ j – 1] = A[0] mit A[ j ] = A[1]: 4 < 8, kein Tausch
zweiter Schritt (j = 2, t = 13)
Array A [4, 8, 2, 11, 13, 17]
Vergleich A [ j – 1] = A[1] mit A[ j ] = A[2]: 8 > 2, 9. Tausch
t = A[ j ] = A[2] = 8
A[ j ] = A[ j – 1] = A[2 – 1] = A[1] = 11 = t
dritter Schritt ( j = 3, t = 11)
Array A [4, 8, 11, 2, 13, 17]
Vergleich A [ j – 1] = A[2] mit A[ j ] = A[3]: 11 > 2, 10. Tausch
t = A[ j ] = A[3] = 2
A[ j ] = A[ j – 1] = A[3 – 1] = A[2] = 11= t
vierter Schritt ( j = 4, t = 11)
Array A [4, 8, 2, 11, 13, 17]
Vergleich A [ j – 1] = A[3] mit A[ j ] = A[4]: 11 < 13, kein Tausch
fünfter Schritt ( j = 5, t = 11)
Array A [4, 8, 2, 11, 13, 17]
Vergleich A [ j – 1] = A[4] mit A[ j ] = A[5]: 13 < 17, kein Tausch
Fünfter Durchlauf, i = 4, Array A [ 4, 2, 8, 11, 13, 17 ]
Im letzten Durchlauf wird die fünftgrößte Zahl 4 in fünf Schritten (n – 1) nach hinten gebubbelt. Der Algorithmus führt wieder fünf Vergleiche und noch eine Vertauschung durch.
erster Schritt ( j = 1, t = 11)
Array A [4, 2, 8, 11, 13, 17]
Vergleich A [ j – 1] = A[0] mit A[ j ] = A[1]: 4 > 2 , 11. Tausch
t = A[ j ] = A[1] = 2
A[ j ] = A[ j – 1] = A[1 – 1] = A[0] = 4 = t
zweiter Schritt ( j = 2, t = 4)
Array A [2, 4, 8, 11, 13, 17]
Vergleich A [ j – 1] = A[1] mit A[ j ] = A[2]: 4 < 8, kein Tausch
dritter Schritt ( j = 3, t = 4)
Array A [2, 4, 8, 11, 13, 17]
Vergleich A [ j – 1] = A[2] mit A[ j ] = A[3]: 8 < 11, kein Tausch
vierter Schritt ( j = 4, t = 4)
Array A [2, 4, 8, 11, 13, 17]
Vergleich A [ j – 1] = A[3] mit A[ j ] = A[4]: 11 < 13, kein Tausch
fünfter Schritt ( j = 5, t = 4)
Array A [2, 4, 8, 11, 13, 17]
Vergleich A [ j – 1] = A[4] mit A[ j ] = A[5]: 13 < 17, kein Tausch
Output Array A [ 2, 4, 8, 11, 13, 17 ]
Der Algorithmus terminiert nach 5 (n – 1) Durchläufen und gibt das sortierte Array A [ 2, 4, 8, 11, 13, 17 ] aus. Insgesamt hat er über alle Durchgänge 25 Vergleiche und 11 Vertauschungen vorgenommen.
**** Pseudocode Bubble-Sort A [11, 13, 4, 17, 8, 2] **** input: A [11, 13, 4, 17, 8, 2] def t = 0 For i = 1 to n-1 do // Äußere Schleife For j = 1 to n-i do // Innere Schleife if A[j-1] > A[j] then t = A[j] A[j] = A[j-1] A[j-1] = t End if End For End For return A
Die Kommentarfunktion ist deaktiviert, aber Trackbacks und Dingbacks sind offen.