Die klassische Klausuraufgabe lautet: "Gegeben das Array [5,1,4,2,8]. Wie sieht es nach jedem Bubblesort-Durchgang aus?". Wir tracen Standard-Bubblesort komplett durch.
Startzustand: [5,1,4,2,8], n=5, also n−1=4 Durchgänge.
Durchgang 1 (i=0, innere Schleife j=0..3):
| Vergleich | Array vorher | Aktion | Array nachher |
|---|
| arr[0]=5 vs arr[1]=1 | [5,1,4,2,8] | 5 > 1, tausch | [1,5,4,2,8] |
| arr[1]=5 vs arr[2]=4 | [1,5,4,2,8] | 5 > 4, tausch | [1,4,5,2,8] |
| arr[2]=5 vs arr[3]=2 | [1,4,5,2,8] | 5 > 2, tausch | [1,4,2,5,8] |
| arr[3]=5 vs arr[4]=8 | [1,4,2,5,8] | 5 < 8, kein Tausch | [1,4,2,5,8] |
Nach Durchgang 1: [1,4,2,5,8]. Die 8 ist garantiert an Position 4 (Schleifeninvariante).
Durchgang 2 (i=1, innere Schleife j=0..2):
| Vergleich | Array vorher | Aktion | Array nachher |
|---|
| arr[0]=1 vs arr[1]=4 | [1,4,2,5,8] | 1 < 4, kein Tausch | [1,4,2,5,8] |
| arr[1]=4 vs arr[2]=2 | [1,4,2,5,8] | 4 > 2, tausch | [1,2,4,5,8] |
| arr[2]=4 vs arr[3]=5 | [1,2,4,5,8] | 4 < 5, kein Tausch | [1,2,4,5,8] |
Nach Durchgang 2: [1,2,4,5,8]. Die hinteren zwei Werte (5, 8) sitzen.
Durchgang 3 (i=2, innere Schleife j=0..1):
Beide Vergleiche keine Tausche. Array bleibt [1,2,4,5,8].
Durchgang 4 (i=3, innere Schleife j=0):
Nur ein Vergleich, kein Tausch. Array bleibt [1,2,4,5,8].
Insgesamt: 4+3+2+1=10=25⋅4 Vergleiche, 4 Tausche. Standard-Bubblesort macht immer alle n(n−1)/2 Vergleiche, auch wenn schon nach Durchgang 2 fertig sortiert. Mit Early-Exit-Flag würde nach Durchgang 3 (kein Tausch) abgebrochen, das spart Durchgang 4.
Schleifeninvariante (Klausur-Klassiker): nach Durchgang i stehen die i größten Elemente sortiert am Ende. Die innere Schleife läuft entsprechend nur bis n−1−i, weil weiter rechts nichts mehr verändert werden muss.
