a = [Implementieren, Sie, den, Sortieralgorithmus, Bubble Sort, in, Python.]
Voraussetzungen:
- Entwicklungsumgebung, wie z.B. Thonny (https://thonny.org/)
- alternativ: Online-Editor, wie z.B. https://www.online-python.com/
Analysieren Sie den dargestellten Ablauf von BubbleSort.
Notieren Sie sich die grundlegenden Ideen des Algorithmus – fertigen Sie eine Beschreibung in Form von Pseudocode an.
Vergleichen Sie Ihre Notizen mit dieser zweiten Darstellung eines Durchlaufes von BubbleSort und prüfen Sie Ihre Lösung auf Ungenauigkeiten.
Nutzen Sie den nachstehenden Code als Vorlage für Ihr Programm.
# BubbleSort
def bubble_sort(liste):
print(liste)
# vom letzten bis zum ersten Index
for _ in range(0):
# für unsortierten Teil der Liste
for _ in range(0):
# tausche, wenn Vorgänger größer als Nachfolger
pass #Platzhalter, kann gelöscht werden
# Initialisiere Liste a
a = [3, 0, 1, 8, 7, 2, 5, 4, 9, 6]
# Starte BubbleSort auf Liste a
bubble_sort(a)In den nebenstehenden Tabs finden Sie gestufte Hilfestellungen, die Sie nutzen können, wenn Sie der Lösung selbst nicht näherkommen.
Es gilt der Grundsatz: Hilfen nur dann nutzen, wenn man zuvor alles probiert hat.
Falls gar kein Lösungsansatz da ist, hier nochmal eine dritte Visualisierung:
Entscheidend ist die richtige Umsetzung der Zählschleifen. Hier gibt es mehrere denkbare Lösungen. Eine mögliche Denkrichtung zur Lösung ist in den Kommentarzeilen beschrieben.
Für alle denkbaren Lösungen benötigt man die Funktion zur Bestimmung der Länge der gegebenen Liste: len(liste)
Zur Bestimmung der richtigen Zählkonditionen, kann man sich denken, dass die Liste im Laufe des BubbleSort-Algorithmus (ähnlich, wie bei SelectionSort) in einen sortierten und einen unsortierten Teil getrennt wird. Eine Zählvariable sollte zur „Mitführung“ des Grenzindex zwischen diesen Teillisten fungieren.
z.B. äußere Schleife: for grenze_i in range (…):
Die äußere Schleife kann lauten:
# vom letzten bis zum ersten Index
for grenze_i in range(len(liste)-1,0,-1):Die innere Schleife sollte dann lauten:
# vom letzten bis zum ersten Index
for grenze_i in range(len(liste)-1,0,-1):
# für unsortierten Teil der Liste
for i in range(grenze_i):
...Tausche benachbarte Elemente (i und i+1) innerhalb der inneren Schleife, wenn der Vorgänger größer als der Nachfolger ist.
Die geschachtelte Schleife lautet vollständig:
# vom letzten bis zum ersten Index
for grenze_i in range(len(liste)-1,0,-1):
# für unsortierten Teil der Liste
for i in range(grenze_i):
# tausche, wenn Vorgänger größer als Nachfolger
if liste[i] > liste[i+1]:
liste[i],liste[i+1] = liste[i+1],liste[i]Testen Sie Ihr fertiges Programm mit Listen unterschiedlicher Länge und Vorsortierung.
Sollten Sie ohne Hilfestellungen ausgekommen sein bzw. nicht alle Hilfen angeschaut haben, dann vergleichen Sie Ihre Lösung mit der aus der 6. Hilfe.
Genießen Sie das gute Gefühl, eine solch schwierige Aufgabe gemeistert zu haben! Programmieren ist nicht immer einfach, aber so erfüllend, wenn man dabei erfolgreich ist.
