Aufgabe 5
Dies ist die fünfte Programmieraufgabe. Du lernst den Algorithmus Quicksort kennen, der Listen mithilfe von Rekursion effizient sortiert.
Aufgabe: Quicksort
In dieser Aufgabe implementierst du den Quicksort-Algorithmus in Python. Der Algorithmus teilt eine Liste in zwei kleinere Listen jeweils eine mit Werten, die kleiner oder gleich einem gewählten Pivotelement sind, und eine mit grösseren Werten – und sortiert diese rekursiv.
Was soll das Programm tun?
- Eine Liste von Zahlen wird im Programm festgelegt.
- Das Programm sortiert die Liste mit Quicksort.
- Es zeigt die unsortierte und anschliessend die sortierte Liste an.
Wie soll sich das Programm verhalten?
Wenn die Liste nur ein oder kein Element enthält, ist sie bereits sortiert.
Ansonsten wählt das Programm das erste Element als Pivotelement, teilt die Liste in zwei Teillisten
(kleiner und groesser) und ruft sich selbst auf, bis die gesamte Liste sortiert ist.
Deine Aufgabe
- Implementiere die Funktion
quicksort(liste). - Wähle ein Pivotelement und teile die restlichen Elemente in zwei Gruppen.
- Sortiere beide Teillisten rekursiv und füge sie zusammen.
- Verwende eine fixe Liste im Code (z. B.
[7, 2, 9, 1, 5, 8, 3]).
Reflexionsfragen
- Was passiert, wenn du das Pivotelement änderst (z. B. das letzte statt das erste)?
- Warum ist Rekursion hier sinnvoll?
- Wie sorgt die Rückgabe für die korrekte Reihenfolge der Elemente?
Tipp: Mit Listenverständnis ([x for x in liste if ...]) kannst du die Teillisten elegant erstellen.