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.
Die innere Schleife soll am Beispiel verdeutlicht werden. Wir greifen dazu die 5te Zeile unserer Abbildung heraus:
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. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
zu | 31.1.2 Implementierung | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
zur Startseite | www.pohlig.de (C) MPohlig 2004 |