Quick Sort in Python
Quick Sort ordnet kleinere und größere Werte relativ zu einem Pivot an.
Was ist Quick Sort?
Quick Sort ordnet kleinere und größere Werte relativ zu einem Pivot an.
Partitioniere Werte um ein Pivot-Element und sortiere die Teilbereiche rekursiv.
Wann wird dieser Ansatz verwendet?
- Algorithmen und Datenstrukturen anhand von ausführbarem Code verstehen.
- Die einzelnen Verarbeitungsschritte und Randfälle nachvollziehen.
- Laufzeit und Speicherbedarf verschiedener Lösungswege vergleichen.
Quick Sort in Python visualisieren
O(n log n)Mit Start oder Schritt kannst du jeden Vergleich und jede Datenbewegung verfolgen.
Beispielcode
main.py
def quick_sort(values):
if len(values) <= 1:
return values
pivot = values[len(values) // 2]
lower = [value for value in values if value < pivot]
equal = [value for value in values if value == pivot]
higher = [value for value in values if value > pivot]
return quick_sort(lower) + equal + quick_sort(higher)
print(quick_sort([10, 7, 8, 9, 1, 5]))Erwartete Ausgabe
[1, 5, 7, 8, 9, 10]So funktioniert es
Die durchschnittliche Laufzeit ist O(n log n). Eine ungünstige Pivot-Wahl kann O(n²) verursachen.
Ändere die Werte und führe das Programm im CodeUtility Python Online-Compiler aus, ohne Python lokal zu installieren.
Übungsaufgaben
Verändere Eingaben und Randfälle, bevor du die Lösung mit größeren Datenmengen testest.
- Teste leere Eingaben, ein Element und doppelte Werte.
- Gib den Zustand nach jedem Schritt aus.
- Vergleiche Laufzeit und Speicherbedarf mit einem alternativen Verfahren.