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 ;-)

[mirage228]

Hi Alex,

mein Infolehrer sagte, dass der Shellsort nicht so schnell, dafür aber relativ kompiziert sei.
Dich mit Quicksort zu beschäftigen wäre eine gute Idee - hast ja meinen Geschwindigkeittest gesehen ;)

mfG
mirage228

[Alexander]

Habe mich gerade schon ein wenig mit Shell-Sort beschäftigt, das mache ich jetzt zu ende ;-). Steht auch schon so mehr oder weniger auf meinem Blatt Papier :mrgreen:
Jetzt muss ich nur noch mal schauen, wann ich das in Delphi "übersetze" bzw. abschreibe ;-)

Ich sollte damit wohl nicht all zu lange warten, sonst blicke ich auf meinem Zettel nämlich nicht mehr durch :? :roteyes: :mrgreen:

PS: Wenn ich ihn richtig verstanden habe, ist er gar nicht so schwer zu verstehen :mrgreen:

[glkgereon]

so, *auch zu wort meld*

erst ma isses ja unterschieldich bei der menge der zahlen, welcher sort jetzt schneller ist..

das sollte man einstellen können...

dann meine werte:
Bubble: 31087,6 705182705
selection: 11668,1 704982704

und dann halt, mehr algo wären schön.... :duck:

[Alexander]

Hi,
klar spielt die Menge der Zahlen eine wichtige Rolle. Aber noch entscheidener ist AFAIK wie die Zahlen angeordnet sind! Denn bestimmte Zahlen Kombinationen oder auch "zufällig vorsortierte" Zahlenfolgen sind bei bestimmten Algos natürlich langsamer oder schneller.
Daher kann man die Messwerte auch nicht wirklich vergleichen, es sei denn man nimmt immer die gleiche Zahlenfolge...

Zitat:

und dann halt, mehr algo wären schön....

Da ich mir hierbei die Sortieralgos hauptsächlich selber erklären will und das möglichst umfassend und vor allem ohne mir einen fremden Source anzuschauen, brauchts natürlich länger als den Source per Copy & Paste ins Projekt einzufügen.
Und da meine Zeit derzeit wieder sehr knapp ist, verzögert es sich leider. Aber wie gesagt es werden mehr kommen. Shell- & Selection-Sort habe ich mir mittlerweile erarbeitet, die sind alle recht einfach zu verstehen und herzuleiten. Nur war ich bisher zu faul, meine Überlegungen nach Delphi zu übersetzen ;-) Vielleicht mache ich es aber heute noch ;-)
Sonst nicht verzweifeln, das Wochenende kommt ja auch noch...

[Alexander]

So dale, habe nun Shell-Sort und Insertionsort mit eingebaut, siehe erster Post...