Insertionsort
Insertionsort ist ein interaktives Experiment in Algorithmen sichtbar gemacht, einer kostenlosen Simulation aus dem StudyFi Lab, die direkt im Browser läuft.
Insertionsort funktioniert wie das Sortieren von Spielkarten in der Hand: Der linke Teil ist schon sortiert, und jedes nächste Element (key) wandert nach links, bis es auf ein kleineres trifft. Größere Elemente rücken dabei eine Stelle nach rechts. Bei zufälligen Daten ist das O(n²), bei fast sortierten fast O(n) — ein sortiertes Array braucht nur n−1 Vergleiche.
Probier das: Lass es auf einem fast sortierten und dann auf einem umgekehrten Array laufen. Wie viel mehr Verschiebungen braucht das umgekehrte?
Häufige Fragen
Was zeigt das Experiment „Insertionsort“?
Insertionsort funktioniert wie das Sortieren von Spielkarten in der Hand: Der linke Teil ist schon sortiert, und jedes nächste Element (key) wandert nach links, bis es auf ein kleineres trifft. Größere Elemente rücken dabei eine Stelle nach rechts. Bei zufälligen Daten ist das O(n²), bei fast sortierten fast O(n) — ein sortiertes Array braucht nur n−1 Vergleiche.
Wie probiere ich „Insertionsort“ aus?
Lass es auf einem fast sortierten und dann auf einem umgekehrten Array laufen. Wie viel mehr Verschiebungen braucht das umgekehrte?
Lernst du für eine Prüfung?
Lade deine Notizen hoch und StudyFi macht daraus Karteikarten, Tests und Podcasts.