Sortieralgorithmen-Benchmark

[tripleeye]

Das Programm berechnet die Zeit, die es für das Sortieren einer Liste von maximal 100000 Elementen mithilfe verschiedener Algorithmen benötigt. Die Liste wird per Random-Button erzeugt.

Das Programm sollte auf allen Windows-BS funktionieren. Getestet wurde es unter Win-XP.

[RavenIV]

Fragen / Anmerkungen zu dem Programm:
- warum sind Bubble-Sort und QSort nicht dabei?
- warum unterscheiden sich die Zeiten bei gleichen Algo und gleicher Datenmenge so gravierend?
- warum hast du die beschränkung der Datenmenge?
- wie zufällig wird die datenmenge erzeugt?
- die Beschriftung der Buttons ist nicht 100% klar
- warum dauert es länger, wenn man eine neu erstellte Datenmenge sortieren lässt?

gruessle

[rantanplan99]

Ich bin zwar nicht der Ersteller des Testprogramms, kann aber ein paar Hinweise zu deinen Fragen geben

Zitat:

Zitat von RavenIV

- warum unterscheiden sich die Zeiten bei gleichen Algo und gleicher Datenmenge so gravierend?
- warum dauert es länger, wenn man eine neu erstellte Datenmenge sortieren lässt?

Die Unterscheiden sich nur beim ersten Ausführen des Tests mit einer neuer Datenmenge. Ich vermute das liegt am Caching. Und alle folgenden Test unterscheiden sich nur minimal (man beachte die Zeitangabe in ms, da kommen sicher Messungenauigkeiten hinzu) Bei mir unterscheiden sich die Testläufe nur im sehr geringen Prozent Bereich (Abgesehen vom aller ersten nach einer neuen Datenmenge).

Aber mal eine Anmerkung zum Programm selbst. Mann kann die Effizienz (bzw. Laufzeit) eines Sortieralgorithmus auch mathematisch bestimmen, dann muss man sich nicht auf so "ungenaue" Methoden der Zeitmessung verlassen.

Man kann zu jedem Algorithmus drei Werte berechnen in Anhängig der Eingabelänge n (Anzahl der zu sortierenden Einträge). Einmal 'bestcase', 'wortcase', und 'avaragecase'. Siehe auch Wikipedia. Das lernt man z.B. an der Uni gleich zu Beginn wenn es um Algorithmen und Datenstrukturen geht.

rantanplan

[shmia]

Zitat:

Zitat von rantanplan99

Mann kann die Effizienz (bzw. Laufzeit) eines Sortieralgorithmus auch mathematisch bestimmen, dann muss man sich nicht auf so "ungenaue" Methoden der Zeitmessung verlassen.

Man kann zu jedem Algorithmus drei Werte berechnen in Anhängig der Eingabelänge n (Anzahl der zu sortierenden Einträge). Einmal 'bestcase', 'wortcase', und 'avaragecase'. Siehe auch Wikipedia. Das lernt man z.B. an der Uni gleich zu Beginn wenn es um Algorithmen und Datenstrukturen geht.

Man kann aber auch bei einer vorgegebenen Menge von Daten die Anzahl der Vergleiche und die Anzahl der Vertauschungen zählen.
Man braucht also nicht Schätzen, sondern man sortiert mit einem bestimmten Algorithmus und zählt einfach mit.
Von einem Sortieralgorithmen Benchmark würde ich genau die Zahlen erwarten.
Ich habe eine Sortier-Basisklasse in der Code-Library, die genau diese Zahlen liefert:
http://www.delphipraxis.net/internal...ct.php?t=34412