Informatikmaterialien 
von Tino Hempel

Startseite | Informatik | Physik | Mathematik | Sonstiges |


Richard-Wossidlo-Gymnasium Ribnitz-Damgarten
Fachbereich Informatik


Sortieralgorithmus Ripplesort


Das Problem des Sortierens großer Datenmengen ist nicht so einfach, wie man schnell glauben kann. Hier steckt eine Menge know how drin!


Das Grundproblem

Beispiel:

In einer Datenbank wurden alle Berge der Erde mit einer Höhe von mindestens 2000 m gespeichert. Man kann sich vorstellen, dass dies sehr viele sind. Nun besteht die Aufgabe, diese Berge nach ihrer Größe zu sortieren. Kein Problem für die Datenbank. Man drückt auf das Knöpfchen und schon ist der Datenbestand sortiert!? Aber wie sortiert der Computer eigentlich und welche Zeit benötigt er dafür?

Gegeben sei also eine Menge von Objekten (i. d. R. Zahlen oder Zeichenketten). Gesucht wird eine Anordnung der Elemente, so dass zwischen je zwei benachbarten Elementen stets die kleiner-gleich-Relation gilt. Es sind nun geeignete Algorithmen zu entwerfen, die dieses Problem möglichst schnell und effizient (Was ist das eigentlich?) lösen. 

Für die programmtechnische Umsetzung soll die zu sortierende Menge als Feld vorliegen.

Sortierverfahren I – Ripplesort

Prinzip des Verfahrens (Visualisierung mittels Programm Sortieralgorithmen in Assembler

Beim Durchlaufen des Feldes wird das erste Element mit allen weiteren Elementen des Feldes verglichen. Ist das gefundene Element kleiner als das erste, so werden diese getauscht. So wird das gesamte Feld einmal durchlaufen und dadurch das kleinste Element gefunden. Nun wird die Prozedur mit dem zweiten Element wiederholt, dann mit dem dritten usw. 

Der Name des Verfahrens beschreibt den Vorgang anschaulich. Die kleinsten Elemente schieben sich wie kleine Wellen nach vorn, so dass die Liste sortiert wird.

Darstellung des Algorithmus als Struktogramm

Experimente zur Untersuchung des Algorithmus

Im Folgenden sollen Experimente zum Laufzeitverhalten des Algorithmus durchgeführt werden. Am Günstigsten ist es, wenn der Leser den beschriebenen Algorithmus in einer Programmiersprache implementiert und einen Zähler für die Anzahl der Vergleiche einbaut. Ein anschauliches Programm findet man unter dem Stichwort Sortierverfahren in Assembler.

1. Untersuchung des Zusammenhangs zwischen der Anzahl der zu sortierenden Elemente n und der Anzahl der Vergleiche V

Wie man hier sehr schön sieht, gilt näherungsweise:

  • Erhöht sich die Anzahl der Elemente um den Faktor 10, so erhöht sich die Anzahl der Vergleiche ca. um den Faktor 100. 
  • Erhöht sich die Anzahl der Elemente um den Faktor 5, so erhöht sich die Anzahl der Vergleiche ca. um den Faktor 25.
  • Erhöht sich die Anzahl der Elemente um den Faktor 2, so erhöht sich die Anzahl der Vergleiche ca. um den Faktor 4.

Das heißt, es gibt wahrscheinlich einen quadratischen Zusammenhang zwischen n und V. Mathematisch ausgerückt V(n) ≈ k·n2, wobei k eine Konstante etwas kleiner als 0,5 ist. 

2. Untersuchung des Zusammenhangs zwischen der Anzahl der Elemente n und der Rechenzeit T

Da im Algorithmus beim Durchlaufen der inneren Schleife stets ein Vergleich auszuführen ist und dieser eine bestimmte Rechenzeit benötigt, wird es sicherlich auch einen mathematisch beschreibbaren Zusammenhang zwischen n und T geben. Dieser wird sich vermutlich genauso verhalten, wie oben untersucht.
Vermutung: T(n) ≈ c·n2.
Prüfung der Vermutung anhand der Zahlenwerte zeigt: c nähert sich für große n tatsächlich einem konstanten  Wert an, hier der Zahl 6,1·10-6

Berechnung des Aufwands

Die Untersuchungen zeigen, dass es vermutlich einen quadratischen Zusammenhang zwischen der Anzahl der Vergleich bzw. der Rechenzeit und der Anzahl der Elemente gibt. Kann dieser Zusammenhang mathematisch bewiesen werden? 

Analysiert man den Algorithmus, so ergibt sich folgendes Bild:

Beim ersten Durchlaufen des Feldes wird das erste Element mit allen weiteren Elementen des Feldes verglichen, also mit n – 1 Elementen. 
Beim zweiten Durchlauf wird das erste Element nicht mehr berücksichtigt, es wird das zweite Element mit den nachfolgenden verglichen, also mit n – 2 Elementen, usw. bis zum letzten Element. Dies gilt offensichtlich auch für den Zeitfaktor T.
Der gesamte Sortiervorgang ist also nach T(n) = (n – 1) + (n – 2) + ... + 2 + 1 Schritten beendet. Diese Summe lässt sich wie folgt umschreiben:

Demzufolge gibt es tatsächlich einen quadratischen Zusammenhang, der hier ziemlich leicht herzuleiten war. Den Informatiker interessiert nun die exakte Formel nicht, ihm genügt die grobe Abschätzung, dass es einen quadratischen Zusammenhang gibt. Als Hintergrund formuliert der Informatiker den Begriff der Zeitkomplexität mit der mathematischen Beschreibung in der O-Notation.

Übung

Man implementiere Ripplesort in der entsprechenden Klasse des Programms Sortieren in Delphi bzw. Java/BlueJ.



zur Startseite
© Tino Hempel 1997 - 2007 Im Web vertreten seit 1994.
Eine Internet-Seite aus dem Angebot von Tino Hempel.

Für alle Seiten gilt der 
Haftungsausschluss/Disclaimer.