Einführung in den Insertion-Sort Algorithmus
Insertion-Sort Algorithmus
Der Insertionsort gehört in der Informatik zu den stabilen Sortieralgorithmen und kann als Sortieren durch Einfügen beschrieben werden, deswegen auch Einfügesortierenmethode genannt. Der Algorithmus ist stabil, arbeitet in-place und kann anhand eines Kartenspiels erläutert werden. Stell dir vor, du bekommst eine Karte nach der anderen gereicht. Du nimmst die erste Karte auf die Hand. Die zweite sortierst du dann links oder rechts davon ein. Die dritte je nach Größe links, dazwischen oder rechts und auch die folgenden Karten jeweils an der richtigen Stelle:
Die Laufzeitkomplexität beim Insertionsort ist im Best-Case O(n) und im Worst-Case O(n2), wobei n die Anzahl der zu sortierenden Elemente angibt.
Lernvideo zum Insertionsort Lernvideo
Hinweis: Alle Ergebnisse und Zwischenergebnisse müssen in Moodle abgegeben werden.
Aufgabe: Insertion-Sort
Schwierigkeitsgrad: Einfach- Gegeben seien folgende Zahlen: 7,6,1,3,9,2,4,8,5
- Sortiere die Zahlenreihe nach dem Insertion-Sort-Algorithmus!
- Gib die Anzahl der Vergleiche/Tausche an.
- Gib die Zeitkomplexität im Best-Case, Worst-Case und im Average an.