Theorieteil zu Folge 8
Insertionsort
Sortieren durch direktes Einfügen
erster Sortierschritt
Der sortierte Teil besteht aus dem ersten Element des Arrays, der unsortierte Teil aus dem Rest-Array. Machen wir uns das wieder an einem Beispiel klar:
|
8
|
5
|
9
|
2
|
1
|
3
|
|
0
|
1
|
2
|
3
|
4
|
5
|
Der sortierte Teil ist grau markiert.
Im ersten Sortierschritt wird nun die erste Zahl des unsortierten Teils genommen und in den sortierten Teil eingefügt - und zwar an der richtigen Position. Die erste Zahl des unsortierten Teils ist die 5. Da gilt: 5 < 8 muss die 5 vor der 8 eingefügt werden:
|
5
|
8
|
9
|
2
|
1
|
3
|
|
0
|
1
|
2
|
3
|
4
|
5
|
Der sortierte Teil ist jetzt um 1 gewachsen.
nachfolgende Sortierschritte
Im Grunde geht es genau so weiter wie beim ersten Sortierschritt beschrieben. Als nächstes muss die 9 in den bereits sortierten Teil eingefügt werden. Da die 9 größer ist als die größte Zahl des sortierten Teils, passiert gar nichts. Lediglich die Grenze zwischen sortiertem und unsortiertem Teil wird um 1 nach rechts verschoben:
|
5
|
8
|
9
|
2
|
1
|
3
|
|
0
|
1
|
2
|
3
|
4
|
5
|
Nun wird die 2 in den sortierten Teil eingefügt. Da sie kleiner ist als die kleinste Zahl des sortierten Teils, wird die 2 noch vor der 5 eingefügt:
|
2
|
5
|
8
|
9
|
1
|
3
|
|
0
|
1
|
2
|
3
|
4
|
5
|
Ähnliches passiert mit der 1:
|
1
|
2
|
5
|
8
|
9
|
3
|
|
0
|
1
|
2
|
3
|
4
|
5
|
Und mit der 3:
|
1
|
2
|
3
|
5
|
8
|
9
|
|
0
|
1
|
2
|
3
|
4
|
5
|
welche zwischen der 2 und der 5 eingefügt werden muss.
Implementierungshinweise
Nicht-optimaler Algorithmus
Ein erster - nicht gut überlegter - Entwurf zur Implementierung des Insertionsort könnte so aussehen: Wir entfernen die erste Zahl des unsortierten Teils aus der Liste:
|
5
|
8
|
9
|
2
|
1
|
3
|
|
0
|
1
|
2
|
3
|
4
|
5
|
wird zu
|
5
|
8
|
9
|
1
|
3
|
|
|
0
|
1
|
2
|
3
|
4
|
|
und dann fügen wir die Zahl an der richtigen Position im sortierten Teil wieder ein:
|
2
|
5
|
8
|
9
|
1
|
3
|
|
0
|
1
|
2
|
3
|
4
|
5
|
Dieser Algorithmus hört sich auf den erste Blick ganz gut an, auf den zweiten Blick jedoch ist er unnötig kompliziert. Das Entfernen von Elementen eines Arrays ist gar nicht so einfach, denn es dürfen ja keine Lücken im Array entstehen. Wird das Element mit dem Index p entfernt, so rückt das Element p+1 eine Position nach links, wird also zu Element p. Entsprechend wird Element p+2 zu p+1 und so weiter, bis das Ende des Arrays erreicht ist.
Auch das Einfügen in einen Array hat mit ähnlichen Schwierigkeiten zu kämpfen. Soll ein Element an der Position p in einen Array eingefügt werden, so müssen alle Elemente, die rechts neben p stehen, um eine Position nach rechts aufrücken. Aus Element p wird Element p+1, aus Element p+1 wird Element p+2 und so weiter.
Besserer Algorithmus
Wir wollen nun einen besseren Algorithmus betrachten. Schauen wir uns dazu mal folgenden Array an:
|
2
|
5
|
8
|
9
|
3
|
7
|
|
0
|
1
|
2
|
3
|
4
|
5
|
Die 3 soll in den sortierten Teil eingefügt werden. Sie wird zunächst mit dem letzten Element des sortierten Teils verglichen. Nun ist die 3 kleiner als die 9, muss also auf jeden Fall links von der 9 eingefügt werden. Daher tauschen wir jetzt die 3 mit der 9:
|
2
|
5
|
8
|
3
|
9
|
7
|
|
0
|
1
|
2
|
3
|
4
|
5
|
Das gleiche machen wir mit der 8. Da die 3 kleiner ist als die 8, muss die 3 links von der 8 eingefügt werden. Also wieder eine Tauschoperation:
|
2
|
5
|
3
|
8
|
9
|
7
|
|
0
|
1
|
2
|
3
|
4
|
5
|
Und jetzt vergleichen wir die 3 mit der 5: Wieder muss getauscht werden:
|
2
|
3
|
5
|
8
|
9
|
7
|
|
0
|
1
|
2
|
3
|
4
|
5
|
Ein letzter Vergleich - 3 mit 2 - kommt zu dem Schluss, dass die Einfügeposition gefunden wurde, denn die 3 ist nicht kleiner als die 2. Damit ist die 3 korrekt einsortiert, und der sortierte Teil kann um 1 wachsen:
|
2
|
3
|
5
|
8
|
9
|
7
|
|
0
|
1
|
2
|
3
|
4
|
5
|
Nach diesen ausführlichen Ausführungen sollten Sie jetzt in der Lage sein, eine entsprechende Methode zu schreiben.
Diese HTML-Seite wurde erstellt von Ulrich Helmich am 1. Oktober 2006.