Musterlösung: Quicksort
Dies ist die fünfte Programmieraufgabe. Die Lösung zeigt, wie Quicksort mit Rekursion,
einem Pivotelement und dem Aufteilen in kleiner/groesser-Listen funktioniert.
Für die Nachvollziehbarkeit verwenden wir eine fixe Liste im Code.
Erklärung der Lösung
Schritt-für-Schritt
1) Abbruchbedingung
if len(liste) <= 1:
return listeListen der Länge 0 oder 1 sind bereits sortiert. Das stoppt die Rekursion.
2) Pivotelement wählen
pivot = liste[0]Hier wird das erste Element als Pivot genutzt. Andere Strategien sind möglich, das Prinzip bleibt gleich.
3) Aufteilen
kleiner = [x for x in liste[1:] if x <= pivot]
groesser = [x for x in liste[1:] if x > pivot]Alle Werte ≤ Pivot nach links, alle > Pivot nach rechts. Das Pivot selbst bleibt in der Mitte.
4) Rekursiv sortieren und zusammenfügen
return quicksort(kleiner) + [pivot] + quicksort(groesser)Die Teillisten werden sortiert und mit dem Pivot zur Gesamtlösung zusammengesetzt.
Was du aus dieser Aufgabe lernst
- Wie Rekursion eine Problemzerlegung in Teilprobleme ermöglicht.
- Wie das Pivotelement die Liste strukturiert.
- Wie Listenverständnis (
[...] for ... if ...) die Aufteilung vereinfacht.