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.

bester Fall Ω(n)
Durchschnitt Θ(n²)
schlechtester Fall O(n²)
Speicher O(1)
stabil
ohne Zusatzspeicher

Was bedeutet das?

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

0 / 372 Schritte

Vergleiche Verschiebungen

Auf Abspielen drücken: Die Linien zeigen, wie die Kosten wachsen

Geschwindigkeit 8 Schritte / s

Leertaste: abspielen oder pausieren. Pfeiltasten links/rechts: Schritt. Pos1 und Ende: springen.

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.