Question 1

Was ist Insertionsort und wie funktioniert es?

Accepted Answer

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.

Question 2

Welche Zeitkomplexität hat Insertionsort?

Accepted Answer

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).

Question 3

Wann sollte man Insertionsort verwenden?

Accepted Answer

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.

Question 4

Welche Vor- und Nachteile hat Insertionsort?

Accepted Answer

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.

Question 5

Ist Insertionsort ein stabiler Sortieralgorithmus?

Accepted Answer

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.

Insertionsort Algorithmus: Einfach erklärt mit Beispielen

Lernkarten zu Sortieralgorithmen: Insertionsort