Steckbrief Bubble Sort
- Zeitkomplexität
- Platzkomplexität
- stabil
- ja
- in-place
- ja
- rekursiv
- nein
Einer der bekanntesten Sortieralgorithmen heisst Bubble Sort. Bubble ist englisch und bedeutet Blase.
Den Algorithmen kann man sich so vorstellen, dass grosse Zahlen in einer unsortierten Liste, wie grosse Seifenblasen aufsteigen und die kleineren Blasen nach unten drücken.
Wenn wir mit Bubble Sort eine Liste sortieren, brauchen wir zwei Indizes. Der Index p (Phase) beginnt beim vorletzten Wert und durchläuft absteigend die Liste.
Das Verfahren basiert auf hintereinander stattfindenden Bubble-Phasen. Innerhalb einer Bubble-Phase werden immer von links beginnend die zwei Werte nebeneinander verglichen.
Dazu brauchen wir den zweiten Index i, der während jeder Bubble-Phase einmal die Liste bis zu p durchläuft. Ist der in der Liste links liegende Wert (der Wert bei i) grösser als der rechts davon (Wert bei i+1), werden diese miteinander vertauscht. Danach werden die nächsten zwei Werte miteinander verglichen.
Am Ende der ersten Bubble-Phase liegt dann der grösste Wert an der letzten Position und p wandert einen Schritt nach unten. Die ganze Prozedur wird dann solange wiederholt, bis p beim ersten Element der Liste angekommen ist.
Beispiel
Das folgende Beispiel illustriert das Verfahren anhand einer unsortierten Liste mit 5 Integer-Werten.
Ziel
| 7 | 5 | 1 | 9 | 2 |
Wenn wir diese Liste nun beispielsweise aufsteigend sortieren, sieht die Liste danach wie folgt aus:
| 1 | 2 | 5 | 7 | 9 |
Ablauf
Wie sortiert Bubble Sort? Wir gehen die Schritte durch:
Aufgaben
Aufgabe: Papier
Wende den Sortier-Algorithmus Bubble Sort auf Papier auf die Liste [7,4,2,9,1] an. Schreibe dabei alle Zwischenschritte und jeweils die Werte für p und i auf (siehe obiges Beispiel)!
Aufgabe: Lückentext
Die folgende Funktion bubble_sort(liste) soll das beschriebene Verfahren implementieren. Leider gibt es einige Lücken im Code. Fülle diese!
def bubble_sort(liste):
for p in range(len(liste)-1,0,-1):
for i in (a)____________:
if (b)____________> (c)____________:
liste[i], liste[i+1] = liste[i+1], liste[i]
2
3
4
5
(a)_______________
(b)_______________
(c)_______________
Aufgabe: Programm
Entpacke das Archiv bubble-sort.zip, öffne das Programm bubble_sort.py und studiere es. Führe es aus und erfahre, wie Bubble Sort verschiedene Listen sortiert.
Füge einen Zähler hinzu, der zählt, wie häufig Werte miteinander verglichen werden. Variiert die Anzahl Vergleiche für verschiedene Listen mit gleicher Länge?
Versuche mit dem Programm unter anderem die folgenden Listen zu sortieren:
liste = [1,5,2,7,9,4,2,1]
liste = [2,6,9,12,15,23]
liste = [23,15,12,9,6,2]
liste = [17,2,12,8,1,9,5,12,7,3,5,4]
2
3
4
Zusatzaufgabe: Optimieren
Ergänze das Programm, so dass der Algorithmus merkt, wenn die Liste sortiert ist und somit vorzeitig abbricht.