2.3 Insertsort

Diese Sortiermethode gehört zu den einfacheren, deren Zeitverhalten proportional zum Quadrat der zu sortierenden Elemente ist. Der Algorithmus geht wie folgt:

Betrachte das erste Element als das schon sotierte Teilfeld und den dahinter befindlichen Rest als das noch unsortierte Feld.

1. Nimm das erste Element des noch unsotierten Teils.
2. Suche die Position, wo das Element in den sotierten Teil eingefügt werden muß.
3. Verschiebe ab dieser Position alle schon sotierten Elemente um 1 nach hinten.
4. Schreibe das Element in die nun freie Position.
5. Führe die Schritte 1 - 4 für das restliche unsortierte Feld durch, das nun ein Element weniger hat.

Dazu ein Beipiel mit folgenden unsortierten Feld:

Wir nehmen an, 3 ist das schon sortierte Feld.

1 ist kleiner als 3, wir müssen 3 um eine Position nach hinten schieben.

Wir setzen 1 in die nun freie Position ein.

Wir fahren mit 2, dem ersten Element des noch unsortierten Rest fort.

2 ist kleiner als 3 und größer als 1, wir schieben die 3 um eine Position nach hinten.

Wir setzen 2 in die nun freie Position ein.

Das letzte Element wurde eingefügt, das Feld ist sortiert.

Ungünstig ist, das in der inneren Schleife Teile des Feldes verschoben werden müssen.

English version not yet available.