Insertionsort
Nachdem Willi nun bereits zwei Sortierverfahren ausprobiert hat, stellt er fest, dass diese immer ganz schön viele Vergleiche benötigen. Gerade bei Selectionsort war Willi ja gezwungen alle noch nicht sortierten Mistkugeln nach der nächstkleineren zu durchsuchen. Dabei wird schnell offensichtlich, dass das manchmal unnötige Arbeit ist, denn manchmal sind Teile der Mistkugeln ja schon zufälligerweise richtig sortiert und die nächste noch-nicht-sortierte Mistkugel ist schon am richtigen Platz.
Willi überlegt sich daher eine entgegengesetzte Strategie: anstatt die nächstgrößte Mistkugel auszuwählen (Selectionsort) möchte er jetzt die nächste benachbarte Kugel an die richtige Stelle innerhalb der bereits sortierten Mistkugelreihe einfügen (Insertionsort). Willi stellt also sicher, dass der rechte Bereich seiner Mistkugelreihe mit jedem Schritt eins größer wird und in sich sortiert bleibt.
Schritt für Schritt
| Gehe vom kleinsten möglichen sortierten Teilarray aus: Die rechteste Kugel ist an ihrem richtigen Platz. |  |
| Wähle nun die nächste benachbarte Kugel, die noch nicht sortiert ist (5). Sortiere sie an die richtige Stelle innerhalb der sortierten Kugeln ein. Nur eine Vertauschung mit (2) ist nötig. |  |
| Wähle die nächste benachbarte Kugel, die noch nicht sortiert ist (1). Innerhalb der sortierten Kugeln befindet sie sich bereits am richtigen Platz wie ein Vergleich mit (2) zeigt. Daher muss man nichts mehr tun. Ein weiterer Vergleich mit Kugeln weiter rechts ist nicht nötig, da man weiß, dass alle Kugel weiter rechts nur noch größer als (2) wären. |  |
| Wähle die nächste benachbarte Kugel, die noch nicht sortiert ist (4). Sie muss einmal mit (1) vertauscht werden und danach ein zweites Mal mit (2). |  |
| Als nächstes muss die (3) korrekt einsortiert werden. Auch hier sind zwei Vertauschungen nötig. |  |
| Da es keine weitere Kugel mehr gibt, die noch nicht einsortiert wurde, ist nun alles fertig sortiert. |  |
(A1)
Sortiere auf einem Blatt Papier mit dem Insertionsort Verfahren die folgende Mistkugelreihe.
(A2)
Wie viele Vergleiche müssen im schlimmsten Fall durchgeführt werden? Gibt es auch einen Fall, bei dem die Kugeln so liegen, dass man viel weniger Vergleiche durchführen muss? Wie viel sind es dann im besten Fall?