Insertion Sort ist ein einfacher stabiler Sortieralgorithmus. Er geht nach dem Prinzip “Sortieren durch Einfügen” vor. Er ist ist ideal, wenn eine sehr gut vorsortierte Folge vorliegt.
Idee
- Die sortierten Elemente befinden sich am Anfang
- Das nächste unsortierte Element wird genommen und absteigend mit den sortierten Elementen verglichen
- Solange es kleiner ist als der linke Nachbar tauscht es mit ihm
Laufzeit
- Best Case:
- Average Case und Worst Case: