Insertion Sort in Python
Insertion Sort ähnelt dem Sortieren von Spielkarten auf der Hand.
Was ist Insertion Sort?
Insertion Sort ähnelt dem Sortieren von Spielkarten auf der Hand.
Füge jedes Element an der richtigen Position in den sortierten Teil ein.
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.
Insertion Sort in Python visualisieren
Mit Start oder Schritt kannst du jeden Vergleich und jede Datenbewegung verfolgen.
Beispielcode
main.py
def insertion_sort(values):
result = values.copy()
for index in range(1, len(result)):
current = result[index]
position = index - 1
while position >= 0 and result[position] > current:
result[position + 1] = result[position]
position -= 1
result[position + 1] = current
return result
print(insertion_sort([9, 5, 1, 4, 3]))Erwartete Ausgabe
[1, 3, 4, 5, 9]So funktioniert es
Größere Werte werden nach rechts verschoben, bis die Einfügeposition frei ist. Für fast sortierte Daten kann das Verfahren sehr effizient sein.
Ä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.