Insertionsort Algorithmus: Einfach erklärt mit Beispielen

Insertionsort ist ein einfacher Sortieralgorithmus, der eine Liste schrittweise sortiert, indem er jedes Element an der richtigen Position in den bereits sortierten Teil einfügt. Der Algorithmus arbeitet ähnlich wie beim Sortieren von Spielkarten in der Hand - man nimmt eine Karte nach der anderen und fügt sie an der passenden Stelle ein.

Insertionsort hat eine Zeitkomplexität von O(n²) im schlechtesten Fall, wenn die Liste in umgekehrter Reihenfolge sortiert ist. Im besten Fall, wenn die Liste bereits sortiert ist, beträgt die Zeitkomplexität nur O(n).

Insertionsort eignet sich besonders gut für kleine Datenmengen (weniger als 50 Elemente) oder wenn die Liste bereits teilweise sortiert ist. Der Algorithmus ist auch nützlich als Baustein in hybriden Sortierverfahren wie Quicksort für kleine Teilarrays.

Vorteile sind die einfache Implementierung, der geringe Speicherbedarf (in-place Sortierung) und die Effizienz bei kleinen oder bereits sortierten Listen. Nachteile sind die schlechte Performance bei großen, unsortierten Datenmengen aufgrund der quadratischen Zeitkomplexität.

Ja, Insertionsort ist ein stabiler Sortieralgorithmus, das bedeutet, dass Elemente mit gleichen Werten ihre relative Reihenfolge beibehalten. Dies ist wichtig beim Sortieren von Objekten mit mehreren Attributen.