|
= Sortieren durch direktes Einfügen
r />
Diese Methode des Sortierens wenden Menschen oft beim Kartenspielen an, um ihre Karten zu sortieren.
Laufzeit:
Der Insertion Sort benötigt im Durchschnitt ungefähr n²/4 Vergleiche und n²/8 Austauschoperationen und im ungünstigsten Fall doppelt so viele.
Funktionsweise:
Betrachtet wird ein Element nach dem anderen und jedes an seinem richtigen Platz, zwischen den bereits betrachteten, eingefügt.
Beschreibung:
In der 1. Zeile erscheint als erste Zahl der 8er, danach der 5er. Da der 5er vor dem 8er in der Reihenfolge der ganzen Zahlen steht, werden die beiden Zahlen vertauscht.
In der 2. Zeile sieht man den 5er, den 8er, den 9er und den 7er. Die ersten drei Zahlen stimmen in der Reihenfolge, nur der 7er nicht. Der 7er wird zwischen dem 5er und dem 8er eingefügt.
In der 3. Zeile findet man 1er, der nicht in die Reihenfolge 5,7,8,9 hineinpaßt. Der 1er wird vor dem 5er eingefügt, usw.
|
