Sortieren durch Einfuegen

31 Sortier-Algorithmen und ihre Implementierung
31.1 Sortieren durch Einfügen
31.1.1 Die Idee

Sortieren einer Zahlenreihe

Bevor wir daran gehen den Algorithmus für eine Stringreihung zu erarbeiten, wollen wir ihn für eine Zahlenreihung studieren.
Die Abbildung (rechts) zeigt eine Reihung von 6 int- Zahlen. Der Algorithmus startet, indem man die zweite Zahl (in der ersten Zeile eingekreist) markiert und prüft, ob sie nach vorne (d.h. nach links) einsortiert werden muss. Dies setzt man fort, bis man bei der letzten Zahl der Reihung angekommen ist. Auf diese Weise kann man garantieren, dass in jeder Zeile, links von der eingekreisten Zahl, eine sortierte Teilliste vorliegt. In der dritten Zeile z.B. "sieht" die <6> eine <5> links von sich. Da die <6> davon ausgehen kann, dass alle Zahlen links von ihr sortiert sind, weiß sie, dass sie an ihrem Platz bleiben muss.
Halten wir fest:
Unser Algorithmus erzeugt, beim 2ten Glied beginnend, mit jedem Schritt eine wachsende sortierte Teilliste, bis man schließlich beim letzten Glied angekommen ist und damit die ganze Reihung sortiert vorliegt.
Wie aber geht das Einfügen in die bereits sortierte Teillisten? Wir erklären den Algorithmus anhand des entsprechenden Pseudocodes.

für index von der zweiten bis zur letzten Zahl in liste tue
//Index ist die Platznummer, an der die umkreiste Zahl, also die Zahl steht, die einsortiert werden soll, alle Plätze links davon enthalten somit die sortierte Teilliste. Die zu Beginn vorliegende, sortierte Teilliste besteht dann aus nur einer Zahl, die die an der ersten Stelle der Reihung steht.

Schlüssel := liste[index]
//Schlüssel hat nun den Wert der Zahl, die umkreist ist, mit Schlüssel wird weitergearbeitet.

// Einfügen in die bereits sortierte Liste liste[1,...,index-1] :
lauf := index-1
//Lauf wird initialisiert und dient dazu die sortierte Teilliste zu durchlaufen
Solange lauf noch eine gültige Platznummer hat und
liste[lauf] > schlüssel
//Das Einsortieren beginnt, "lauf" läuft nach links, bis die Stelle gefunden ist, an der "Schlüssel" einsortiert werden muss, spätestens jedoch auf den ersten Platz der Reihung

liste[lauf+1] := liste[lauf]
//An dieser Stelle ist klar, dass "Schlüssel" einsortiert werden muss und nicht an seinem Platz bleiben kann. Die Zahl an der Stelle "lauf" rückt nach rechts. Unsere Zahl liste[index] geht verloren, ist aber in "Schlüssel" gerettet.
lauf := lauf - 1 //Ist lauf vor der ersten Stelle angekommen, dann muss das
erste Zeichen durch Schlüssel überschrieben werden und die Schleife ist fertig.
// Lauf wird weiter nach links gerückt.
Somit rücken alle schon sortierten Zahlen nach rechts, bis am Ende der Schleife die Stelle gefunden ist, an der "Schlüssel" schließlich eingefügt werden muss.

liste[lauf+1] := schlüssel
// hochsortiertes Glied wird eingefügt

Die innere Schleife soll am Beispiel verdeutlicht werden. Wir greifen dazu die 5te Zeile unserer Abbildung heraus:

1	Inhalt d. Reihung	1	2	4	5	6	3	index=5 / lauf=4 / schlüssel=3 Einstieg in Schleife da liste[lauf] > Schlüssel
	Platznummern	0	1	2	3	4	5
2	Inhalt d. Reihung	1	2	4	5	6	6	index=5 / lauf=4 / schlüssel=3 liste[lauf+1]=a[lauf] Verbleib in der Schleife da liste[lauf] > Schlüssel
	Platznummern	0	1	2	3	4	5
3	Inhalt d. Reihung	1	2	4	5	6	6	lauf=lauf-1 index=5 / lauf=3 / schlüssel=3
	Platznummern	0	1	2	3	4	5
4	Inhalt d. Reihung	1	2	4	5	5	6	liste[lauf+1]=liste[lauf] index=5 / lauf=3 / schlüssel=3 Verbleib in der Schleife da liste[lauf] > Schlüssel
	Platznummern	0	1	2	3	4	5
5	Inhalt d. Reihung	1	2	4	5	5	6	lauf=lauf-1 index=5 / lauf=2/ schlüssel=3
	Platznummern	0	1	2	3	4	5
6	Inhalt d. Reihung	1	2	4	4	5	6	liste[lauf+1]=A[lauf] index=5 / lauf=2 / schlüssel=3
	Platznummern	0	1	2	3	4	5
7	Inhalt d. Reihung	1	2	4	4	5	6	lauf=lauf-1 index=5 / lauf=1 / schlüssel=3 Aussieg aus der Schleife da liste[lauf] > Schlüssel falsch
	Platznummern	0	1	2	3	4	5
8	Inhalt d. Reihung	1	2	3	4	5	6	liste[lauf+1]=Schlüssel index=5 / lauf=1 / schlüssel=3
	Platznummern	0	1	2	3	4	5

Achtung: Die Anweisung lauf=lauf-1 geht natürlich nur dann, wenn lauf > 0 ist. Falls lauf = 0 ist, wird dort einsortiert und "lauf" braucht nicht mehr dekrementiert werden. Würde man in diesem Fall aber "lauf" weiter dekrementieren, käme es zu einem Laufzeitfehler, da der Index von Reihungen keine negativen Werte annehmen darf.

31.1.2 Implementierung

zur Startseite