Algorithmen und Datenstrukturen I
Projekt 1: Laufzeitmessung von Sortieralgorithmen
Um die Verschiedenen Algorithmen miteinander vergleichen zu können, habe ich mir
ein kleines Programm geschrieben, dass die Laufzeit verschiedener Algorithmen miteinander
vergleicht.
Debug-Modus
Wird das Programm im Debug-Modus gestartet, so wird jeder Algorithmus der Reihe nach mit
einem Array der Größe 15 gestartet und die einzelnen Sortierschritte ausgegeben. Damit
kann man nachprüfen, ob ein Algorithmus korrekt arbeitet.
Speziell für den QuickSort gibt es eine gesonderte Ausgabe: Die einzelnen Teilarrays
werden in eckigen Klammern gekennzeichnet und der Rest des Arrays wird ausgeblendet. Dabei
wird als Schrittnummer das Referenz-Element ausgegeben. Am
Ende jeden Schrittes wird dann das komplett bearbeitete Array ausgegeben. Dabei wird als
Schrittnummer eine 0 ausgegeben.
Bei Shell-Sort werden als Schritt jeweils die Schrittweiten des jeweiligen Durchlaufes angezeigt.
Normaler Modus
Im normalen Betriebsmodus wird zunächst die Anzahl der Wiederholungen abgefragt. Als Laufzeit wird dann
der arithmetische Mittelwert aller Durchläufe angezeigt. Dann werden alle Algorithmen auf zufällig erzeugte
und dannach auf sortierte Arrays der Größe 10.000 angewandt und jeweils die Laufzeiten ausgegeben.
Programm-Download
Laufzeitmessung für Sortieralgorithmen 0.1b
(Größe: 57 kB | Stand: 11.09.2003 | Downloads: 1300
)
Die aktuelle Version wird noch mit allen Debug-Informationen unter VC++ 5.0
compiliert. Alle anderen Varianten der Compilierung erzeugen zwar genauere Werte, sind aber
zum testen des Programmes nicht akzeptabel.
Wer Probleme mit der Laufzeitmessung bei den schnellen Algorithmen hat, der sollte die Konstante
"WERTE" auf einen höheren Wert setzen. Dann werden allerdings die langsammen Algorithmen erheblich
langsammer.
|