Insertionsort
Baut links einen sortierten Teil auf, einen Wert nach dem anderen. Jeder neue Wert wird herausgenommen und nach links geschoben, bis er auf einen kleineren trifft.
- Ω(n)
- Θ(n²)
- O(n²)
- O(1)
- ja
- ja
Bester Fall: wie die Zeit mit der Listengröße n wächst, wenn die Eingabe für diesen Algorithmus am einfachsten ist.
Durchschnitt: das übliche Wachstum der Zeit mit n. Bei n² dauern doppelt so viele Werte etwa viermal so lang. n log n wächst viel langsamer.
Schlechtester Fall: das Wachstum bei der schwierigsten Eingabe. Wichtig, wenn das Tempo nie einbrechen darf.
Speicher: wie viel Zusatzspeicher neben der Liste nötig ist. 1 heißt ein paar Variablen, n heißt eine Kopie der Liste.
Stabil: Zwei gleiche Werte behalten ihre ursprüngliche Reihenfolge. Wichtig, wenn man Datensätze nach einem Feld sortiert.
Ohne Zusatzspeicher: sortiert direkt in der Liste, ohne zweite Liste.
- wird verglichen
- wird verschoben
- in der Hand
- sortierter Teil
- am endgültigen Platz
Probieren Sie es aus: Wählen Sie eine fast sortierte Liste. Fast nichts muss rücken, also ist es nach sehr wenigen Schritten fertig.
So funktioniert es
Der linke Teil ist immer sortiert. Der nächste Wert wird herausgenommen. Jeder größere Wert im sortierten Teil rückt einen Platz nach rechts, dann kommt der Wert in die Lücke. So sortieren viele Menschen Spielkarten in der Hand.
Wann es sich eignet
Gut für kurze Listen und für fast sortierte Listen, dort ist es sehr schnell. Echte Sortierbibliotheken nutzen es in schnelleren Verfahren für die kleinen Stücke einer Liste.