Vergleich von verschiedenen Sortieralgorithmen

[Alexander]

Hallo,
ich habe gerade ebend ein kleines Progrämmchen geschrieben, was den Sortieralgo Selectionsort mit Bubblesort vergleicht. Nichts aufwendiges und aufregendes also.
Irgendwann kommen sicherlich noch weitere Sortieralgos hinzu. Aber ich muss sie mir erst noch anschauen und dafür fehlt leider die Zeit :sad:. Bubblesort und Selectionsort sind ja recht einfach (und langsam), die brauch man sich nicht anzuschauen, um sie zu verstehen. Die kann man prima selber erarbeiten. ;-)

Bei der Performancemessung habe ich mich bei Hagen bedient (;-)). Es wird also nicht mit getTickCount verglichen.

Source und EXE sind im Anhang.

Edit: Ich habe jetzt endlich Insertion-Sort und Shell-Sort implementiert. Irgendwann werde ich noch weitere einbauen, aber derzeit fehlt mir leider die Zeit.

Edit 2: Titel leicht angepasst. Vorher: "Vergleich von Bubblesort und Selectionsort"

[mirage228]

Hi,

dir fehlt der VAR Parameter in den Sortierprozeduren, somit werden die Sortierergebnisse nie zurückgeschrieben (-> Es werden die unsortiereten Zahlen angezeigt).

Meine Ergebnisse (in MS)

Bubblesort: ~ 70000 ms
Selectionsort: ~ 25000 ms
Quicksort: ~ 25 ms (von mir eingebaut)

mfG
mirage228

[Alexander]

Hi,
danke für's testen.
Das die Ergebnisse zurückgeschrieben werden, war ehrlich gesagt auch gar nicht meine Absicht, wollte nur ebend die Zahlen anzeigen lassen...
So große Zeitunterschiede zwischen bubblesort und selectionsort waren allerdings bei mir nicht ;-).

[Luckie]

Ohne den Quelltext groß anzukucken, wie misst du denn die Zeiten? Mit GetTickCount? Dann ist das auf unterschiedlichen Systemen wertlos, da GetTickCount auch die Zeit misst, die dein Thread mit warten darauf verbringt wieder Rechenzeit zu geteilt zu bekommen und wenn viele andere Prozesse laufen und welche mit höherer Priorität dann kann dass schon mal ein paar Millisekunden dauern.

Ah, sehe gerade du machts es mit Hagens Code.

Nur beim Sortieren, reagiert dein Programm nicht mehr.

[Alexander]

Jo. Ich mache das mit Hagen's Code. GetTickCount war mir auch zu "unsicher".

Das Programm reagiert deswegen nicht mehr, weil ich das Sortieren nicht in einen eigenen Thread ausgelagert habe, mal schaun vielleicht ändere ich das noch ;-)

[Stanlay Hanks]

Hi. Also bei mir ist der Unterschied auch nicht klein :gruebel:

Bubblesort: 40268,5 ms (Vergleiche: 705182705)
Selectionsort: 13706,5 ms (Vergleiche: 704982704)

Man liest sich, Stanlay :hi:

[negaH]

@Alexander, nur weil du meine Routinen nutzt heist das aber noch nicht das Luckie's Aussage damit nicht mehr zuträfe. Die "Unabhängigkeit" vom Tasksystem des OS bezieht sich in den Routinen ausschließlich nur auf das Ausmessen und Ermitteln der CPU Taktfrequenz, aber nicht auf die einzelnen Messungen. D.h. auch mit diesem Routinen werden die Taktzyklen innerhalb von schlafenden Threads weiter mitgezählt. Deshalb und auch im generellen kann man unter Windows KEINE Absolutmessungen durchführen, das geht einfach nicht (bzw. es geht nur hypothetisch). Du kannst aber sehr wohl die relativen Geschwindigkeits-Unterschiede von einer Funktion zu einer anderen ermitteln. Unter der Voraussetzung das die Messzeit lang ist und somit in beiden Messungen das Betriebssystem gleichoft zum Zuge kommt.

Gruß Hagen

[Alexander]

Hallo Hagen,
Danke dass du das noch mal betonst :-).
So meinte ich das allerdings auch nicht. Du hast ja in deinem Kommentar im Sourcecode geschrieben das deine Methode theoretisch x mal genauer ist als getTickCount. Und darauf habe ich mich im Prinzip bezogen. Das eine 100%ig Genauigkeit nicht erreicht werden kann, ist mir durch aus bewusst.

Hierbei geht es ja auch nur um den direkten Vergleich, um zu sehen, dass Selection-sort i.d.R. wersentlich schneller ist als der Bubblesort. Daher ist die 100%ige Genauigkeit auch nicht erforderlich ;-)

Grüße, Alexander

PS: Ich schau mir morgen wohl mal das Prinzip des Shell-Sorts an und baue ihn evtl. noch mit ein... (wenn ich ihn denn verstehe :zwinker: :mrgreen: )

[negaH]

Hm, wenn du lernen willst ok, ansonsten verschwende nicht deine Zeit und stattdessen beschäftige dich mit den verschiedenen Quicksort Verfahren. Diese sind theoretisch die schnellsten Verfahren (neben Heapsort) aber asymptotisch nur so schlecht wie einfacher Bubblesort. Der Vorteil gegenüber Heapsort ist eben das Quicksort sehr Resourcenschonend ist. In meiner langjährigen Erfahrung bin ich mit Insertion Sort für kleinere Sortierungen mit sehr wenigen Elementen sehr gute gefahren. Bei größeren Listen nutze ich immer Quicksort mit Primoraler Teilung und Insertion/Merge Sort im innersten rekursiven Funktionsaufruf.

Gruß Hagen

[Alexander]

Hi,
ich werde mir demnächst, auch noch mal die anderen Sortieralgos (insbesondere auch Quicksort) anschauen und versuchen mehr oder weniger selber zu entwickeln und vor allem zu verstehen. Das war mehr oder weniger der Einstieg (bzw. zur Erinnerung, habe mich schon mal vor Jahren mit Sortieralgos beschäftigt, aber nicht all zu viel verstanden, war wohl noch zu jung...).
Als nächstes kommt wie gesagt der Shell-Sort. So ungefähr weiß ich auch schon wie er funktioniert (noch von damals, ich glaub ich war 12 oder 13 :shock:), allerdings muss ich mir das noch mal genauer anschauen, um ein Delphi-Code oder auch einen allgemeinen zu schreiben...
Wenn ich mich recht erinnere, werden die Zahlen (oder was auch immer), in kleineren Listem/Arrays vorsortiert, dann immer wieder vergrößert und sortiert bis man das vollständige Array hat. Sortiert wird AFAIK mit Insertion-Sort.
Naja ich schaue mal, nur rennt mir irgendwie die Zeit immer davon...

PS: Aber danke für deinen Rat ;-)