Praxisteil zu Folge 8
Zeitverhalten der Sortieralgorithmen
Allgemeines zum Messen von Zeitverhalten
Wir wollen nun das Zeitverhalten der drei Sortieralgorithmen auf ganz einfache Weise miteinander vergleichen. Experimente mit der "inneren Uhr" des Rechners haben sich in der Vergangenheit als nicht sehr zuverlässig erwiesen, da bei einem Multitasking-Betriebssystem wie Windows 2000 oder MacOS 10 sich dauernd alle möglichen Prozesse in die Quere kommen, die das Zeitverhalten eines Sortieralgorithmus beeinflussen. Hier sehen sie einen Auszug aus der Aktivitätsanzeige meines privaten Rechners:
Die Liste ist noch viel länger, aber mein Monitor bildet nur 1280 Zeilen ab...
Unsere Methode ist einfacher
Daher verfolgen wir hier einen radikal anderen Ansatz, der auch recht einfach zu verstehen und vor allem zu implementieren ist: Wir bauen einfach Zähler für Vergleiche und Zuweisungen in den Quelltext der Klasse Liste ein und haben dann ein rechnerunabhängiges Maß für die Zeit, die der Algorithmus für das Sortieren von Zahlen benötigt.
Betrachten Sie dazu folgenden Quelltext-Auszug aus der Klasse Liste:
Die Klasse Liste wurde um zwei Attribute vergleiche und zuweisungen ergänzt. Jedes mal, wenn im Laufe des Bubblesort zwei Zahlen miteinander verglichen werden, wird das Attribut vergleiche inkrementiert, und bei der Zuweisung wird das Attribut zuweisungen um Eins erhöht. Das kann man zum Beispiel gut bei der Methode tauschen() sehen. Ein Tauschprozess besteht aus drei Zuweisungen, daher wurde der Quelltext der Methode tauschen() um die Anweisung
zuweisungen += 3;
ergänzt, welche das Attribut zuweisungen um 3 inkrementiert.
Ein besonders interessanter Fall sind die for-Schleifen. Betrachten wir den Kopf einer for-Schleife näher:
for (int i = 0; i < 19; i++)
Die Laufvariable i muss nur am Beginn der for-Schleife deklariert und initialisiert werden. Daher muss das Attribut zuweisungen um 1 erhöht werden (Zeile 42).
Die Schleifenbedingung i < 19 wird vor jedem Schleifendurchlauf überprüft. Daher muss das Attribut vergleiche am Anfang eines jeden Schleifendurchlaufs um 1 erhöht werden (Zeile 45). Am Ende eines jeden Schleifendurchlaufs wird die Laufvariable um 1 erhöht, also wirkt sich das auf die Anzahl der Zuweisungen aus (Zeile 46).
In Zeile 48 wird das Attribut vergleiche inkrementiert, weil ja als nächste Anweisung eine if-Abfrage kommt. Streng genommen müssten auch Methoden-Aufrufe protokolliert werden, weil diese ja ebenfalls Rechenzeit kosten. Aus Übersichtsgründen habe ich in meinem Quelltext aber darauf verzichtet.
Übung 8.5 (4 Punkte)Speichern Sie Ihr Projekt unter einem neuen Namen und ergänzen Sie dann die drei Sortieralgorithmen entsprechend! |
Visualisierung des Sortierens
Jetzt stellt sich die Frage, wie die Visualisierung der Sortierzeiten erfolgen soll. Dazu verwenden wir ein kleines Java-Applet, das ich Ihnen zunächst einmal im Bild zeigen möchte:
Das Applet
Betrachten wir einfach mal den Quelltext des Java-Applets:
Die sehr ausführliche Besprechung des Quelltextes wurde in einge eigene Datei ausgelagert.
Übung 8.6 (4 Punkte)Bringen Sie das Java-Applet zum Laufen. Sie müssen auch die Methode balkendiagramm() der Klasse Liste noch etwas verschönern. Zum Beispiel müssen die Vergleiche und Zuweisungen ausgegeben werden. Außerdem muss das Diagramm nach jedem Buttonklick neu gezeichnet und vorher gelöscht werden. Das können Sie auch in balkendiagramm() einbauen. |
Übung 8.7 (3 Punkte)Erfassen Sie das Zeitverhalten der drei Sortieralgorithmen systematisch und protokollieren Sie es. Es reicht nicht aus, sich die Ergebnisse von einem einzigen Bubblesort anzuschauen. Die Zahl der Rechenoperationen hängt natürlich von der Verteilung der Zufallszahlen ab. Es sind also mehrere Versuche notwendig (mindestens 10), und erst dann kann man Mittelwerte für jeden Algorithmus bilden. |
Übung 8.8 (6 Punkte)Bisher haben wir nur das Verhalten der drei Algorithmen für genau 20 Zahlen untersucht. Interessant wird es aber, wenn wir unterschiedlich große Arrays analysieren. Wie hängt die durchschnittliche (!) Sortierzeit von der Größe des Arrays ab? Überlegen Sie sich selbst, wie Sie praktisch vorgehen wollen, und erstellen Sie dann eine fundierte Graphik: X-Achse = Größe des Arrays (10, 20, 50, 100, 200, 500, 1000), Y-Achse = durchschnittliche Sortierzeit (Anzahl der Zuweisungen + Anzahl der Vergleiche, Mittelwert aus mehreren Messungen). Sie können auch gern ein völlig neues Applet schreiben, welches all diese Aufgaben für Sie automatisch erledigt. |
Zurück zur Folge 8
Diese HTML-Seite wurde erstellt von Ulrich Helmich am 3. Oktober 2006.