Erklärung:

Der Algorithmus Insertion Sort funktioniert vom Prinzip wie das Sortieren eines Kartenstapels.
Auf der Hand haben wir die sortierten Karten. Wir nehmen uns eine Karte vom unsortierten Kartenstapel
und stecken diese zwischen die sortierten Karten an die passende Position. Somit verschieben sich
logischerweise alle Karten rechts neben der eingefügten Karte um eine Stelle.

Insertion Sort arbeitet mit 2 Schleifen, einer inneren und einer äußeren Schleife.
Die 2te Schleife (im folgenden Bsp. "j") geht vom 2ten bis zum letzten Feld des Arrays und wählt das nächste
Element aus, dass in den sortierten Teil eingefügt werden soll. (dieses wäre im Fall unseres Kartenspiels
immer die oberste Karte des Stapels) Da ein Wert alleine immer "sortiert" ist fängt diese Schleife beim 2ten Element an.
Die innere Schleife läuft von j bis zum ersten Element und vertauscht das selektierte Element mit dem links daneben
stehenden, falls dieses kleiner sein sollte.

Dies wird anhand des Beispiels vielleicht noch etwas deutlicher.

Beispiel:


Schritt 1: Das erste Element ist bei Insertion Sort automatisch sortiert, daher steht der Zähler der 2ten Schleife ( j ) auf dem 2ten Feld


Schritt 2: Das 2te Element wird selektiert und mit dem Element links daneben verglichen. Ist das Element kleiner, so werden die Elemente vertauscht


Schritt 3: In diesem Fall ist die 5 das größere Element, daher werden die Elemente nicht vertauscht. Die 5 wird wieder deselektiert und der Zeiger j springt aufs nächste Feld


Schritt 4: Die innere Schleife ( i ) wird gleich der äußeren Schleife ( j ) gesetzt


Schritt 2: Die 3 wird selektiert und mit der 5 verglichen


Schritt 3: Da die selektierte 3 kleiner ist werden die beiden Elemente vertauscht


Schritt 2/3: Die selektierte 3 wird mit dem Element davor verglichen. Da die 3 aber größer ist als die 2 werden diese nicht vertauscht und der Zeiger ( j ) springt auf das nächste Feld


Schritt 4: Die innere Schleife ( i ) wird gleich der äußeren Schleife ( j ) gesetzt


Schritt 2 bis 4 wiederholen bis das Array komplett sortiert ist.

Die eins wird nun mit der 5 vertauscht, danach mit der 3 und dann noch mit der 2, da alle Zahlen
größer als die 1 sind. Eigentlich ganz simpel, oder? :)

Aufwand:

Insertion Sort benötigt bei einem durchschnittlichen Datensatz etwa O(n²/4) Vergleiche und O(n²/8) Vertauschungen.

>> Allgemeine Fragen oder Probleme mit dem Tutorial? Hier gehts zum Forum!