Hello,
today I have finished a program that allows it to compare miscellaneous sorting algorithms. It has two kinds of display: a tabular and a graphical one. Furthermore you can switch between two languages, english and german (if your windows user lange is German, the german language strings are used; the english ones otherwise).
In the tabular representation you can compare how the implemented algorithms behave under certain conditions (presorting and size of the data). The comparable criteria are the number of comparisons / exchanges, the needed time and the additional allocated memory. The results are displayed in form of a table and can be copied to the clipboard or saved in a file.
The graphical representation allows to watch the different algorithms during sorting. The representation can be created using lines or points. It is possible to set delays at certain positions (after each pass, after each comparison, after each exchange) to facilitate the tracking of the sorting process. If 'after each comparison' is selected the compared elements will be marked, so that the process is even better to understand.
09.05.2004: The Win2000 bug is fixed now.
The source code can be downloaded here.
Comments are welcome.
Regards, Marwin
today I have finished a program that allows it to compare miscellaneous sorting algorithms. It has two kinds of display: a tabular and a graphical one. Furthermore you can switch between two languages, english and german (if your windows user lange is German, the german language strings are used; the english ones otherwise).
In the tabular representation you can compare how the implemented algorithms behave under certain conditions (presorting and size of the data). The comparable criteria are the number of comparisons / exchanges, the needed time and the additional allocated memory. The results are displayed in form of a table and can be copied to the clipboard or saved in a file.
The graphical representation allows to watch the different algorithms during sorting. The representation can be created using lines or points. It is possible to set delays at certain positions (after each pass, after each comparison, after each exchange) to facilitate the tracking of the sorting process. If 'after each comparison' is selected the compared elements will be marked, so that the process is even better to understand.
09.05.2004: The Win2000 bug is fixed now.
The source code can be downloaded here.
Comments are welcome.
Regards, Marwin
Excellent! A great learning tool and very well designed and written. Good job! :alright:
I just had a problem, though, if i go to the tabular representation, select "Quicksort" and presorting as 'sorted ascending' then with 50000 or more elements the program eventually exits unexpectedly.
Also, how about adding bogosort (http://en.wikipedia.org/wiki/Bogosort) to the algorithms? :grin:
Also, how about adding bogosort (http://en.wikipedia.org/wiki/Bogosort) to the algorithms? :grin:
two thumbs up :alright: :alright:
Hey, like it !!!! Whot jimmy said. (two|both thumbs up!!!!!!)
Elements: 50000000
Initialization value: 255
Presorting: Unsorted
Algorithm Comparisons Exchanges Time(ms) Memory in byte
Shellsort 8029890575 8050766817 81922
2-Way Mergesort 1216417768 2471723749 19328 200000000
Straight 2-Way Mergesort 1220034594 2471593961 19328 200000000
Natural 2-Way Mergesort 2445357663 2410955548 25125 200000000
Radix Exchange-Sort 1598689458 228018417 10078
Quicksort 1654512499 420599396 11390
Straight Quicksort(masm32.lib) 1664384567 468632866 11828 50000040
Combsort (masm32.lib) 3683333547 493118346 28578
Pre-Sorted: ascending
Algorithm Comparisons Exchanges Time in ms
Shellsort 620173843 620173843 5360
2-Way Mergesort 650667584 1301335168 7938
Straight 2-Way Mergesort 651076032 1302152064 8953
Natural 2-Way Mergesort 49999999 0 281
Radix Exchange-Sort 1600000000 0 7953
Quicksort (don't try it!)
Straight Quicksort(masm32.lib) 1282227869 116113921 6750
Combsort (masm32.lib) 2883333563 0 17844
Pre-Sorted: descending
Algorithm Comparisons Exchanges Time in ms
Shellsort 1214780463 1248219023 8141
2-Way Mergesort 632223552 1915114688 11969
Straight 2-Way Mergesort 632223552 1915523136 14500
Natural 2-Way Mergesort 1932223526 1915523136 19110
Radix Exchange-Sort 1600000000 25000000 7969
Quicksort (don't try it!)
Straight Quicksort(masm32.lib) 1282227896 141113924 6797
Combsort (masm32.lib) 2983333561 195092986 19343Thank you all for your feedback!
I just had a problem, though, if i go to the tabular representation, select "Quicksort" and presorting as 'sorted ascending' then with 50000 or more elements the program eventually exits unexpectedly.
Also, how about adding bogosort (http://en.wikipedia.org/wiki/Bogosort) to the algorithms? :grin:
Thank you for reporting this bug, I've never noticed it yet although I tested already 20.000.000 elements. I'll take a look at it. What OS do you use?
Bogosort? :) I am sure I won't implement it. This url has convinced me! :)
bitRAKE, what about using only 20.000.000 elements? I have only 256MB RAM, so I can't run the program with 50.000.000 elements (a double word is allocated for each element => 50.000.000*4=200.000.000 => 200MB RAM). That means the results on my PC won't be realistic, because WinXP would access the HDD too often. ;)
Thanks and regards,
Marwin
I just had a problem, though, if i go to the tabular representation, select "Quicksort" and presorting as 'sorted ascending' then with 50000 or more elements the program eventually exits unexpectedly.
Also, how about adding bogosort (http://en.wikipedia.org/wiki/Bogosort) to the algorithms? :grin:
Thank you for reporting this bug, I've never noticed it yet although I tested already 20.000.000 elements. I'll take a look at it. What OS do you use?
Bogosort? :) I am sure I won't implement it. This url has convinced me! :)
bitRAKE, what about using only 20.000.000 elements? I have only 256MB RAM, so I can't run the program with 50.000.000 elements (a double word is allocated for each element => 50.000.000*4=200.000.000 => 200MB RAM). That means the results on my PC won't be realistic, because WinXP would access the HDD too often. ;)
Thanks and regards,
Marwin
It crashes on my win2k pc :(
Thanks clippy, now I hear it twice that the program makes troubles under Win2000 but as I own only Win98 and WinXP I can't track the bug. Could you please post the offset where the exception occures and some other informations, too (if available)?
Regards, Marwin
Regards, Marwin
stormix, Quicksort (as it is implemented here: recursive, not median-of-three) *isn't very usefull* when used to sort sorted or nearly sorted data (as bitRAKE already mentioned). The problem is a stack overflow, right now I don't know how to solve this bug but I'll find a solution (I hope so ;) ).
Regards, Marwin
Regards, Marwin
Marwin, I had some time to play with the graphical display - it was enjoyable to see how the algorithms work visually. I appreciate the effort you have put into this. Attached is the results.
Even thought comparison consist of two reads and one subtraction; and exchanges consist of two reads and two writes -- if we assume the operation of comparison and exchange take the same amount of time we see something seemingly strange. Not only do the fastest algorithms do less operations, but they are also doing the least number of operations per ms. The reason for this is more code is running to assist in not accessing memory.
Even thought comparison consist of two reads and one subtraction; and exchanges consist of two reads and two writes -- if we assume the operation of comparison and exchange take the same amount of time we see something seemingly strange. Not only do the fastest algorithms do less operations, but they are also doing the least number of operations per ms. The reason for this is more code is running to assist in not accessing memory.
Hi Marwin
I too had a crash on Win2k, and this pops up:
I too had a crash on Win2k, and this pops up:
It's a pretty nice toy, Marwin :alright: . I guess it would be nice if you could visualize more elements, but it's not too important - nice that you added the delay feature :)
Shark, you'll probably need a stack dump or trace the app, that address is in kernel-land.
Shark, you'll probably need a stack dump or trace the app, that address is in kernel-land.
Marwin, I had some time to play with the graphical display - it was enjoyable to see how the algorithms work visually. I appreciate the effort you have put into this.
Thank you bitRAKE.
Originally posted by bitRAKE
The reason for this is more code is running to assist in not accessing memory.
The reason for this is more code is running to assist in not accessing memory.
Yes, that's right. But the inner loop of QuickSort is very small, and it is still "slower" (160 ms per 20.000.000 elements) than Radix Exchange-Sort. That's because Radix Exchange-Sort needs less exchanged than QuickSort.
I have to mention that exchanges aren't exchanges every time. I increment the counter, too, when an element is moved (for example in Insertionsort).
Originally posted by f0dder
[...] nice that you added the delay feature
[...] nice that you added the delay feature
Thanks f0dder. Well, what use would it have if you're running one of the faster algorithms without having a delay. You won't see anything from the sorting process. ;)
I too had a crash on Win2k, and this pops up:
---
Shark, you'll probably need a stack dump or trace the app, that address is in kernel-land.
---
Shark, you'll probably need a stack dump or trace the app, that address is in kernel-land.
I hope I'll get access to an computer with Win2000 installed soon.
Regards, Marwin
Here is what OllyDbg says:
Thanks for the effort SharK, but what I need is the API function (and the position where in the program it is called) that is called.
Regards, Marwin
Regards, Marwin
It happens, when your program calls DialogBoxParam.
When I trace, from where your program calls that API function,
this is where I go, and it never returns from the call to that API:
When I trace, from where your program calls that API function,
this is where I go, and it never returns from the call to that API:
Yes, that's right. But the inner loop of QuickSort is very small, and it is still "slower" (160 ms per 20.000.000 elements) than Radix Exchange-Sort. That's because Radix Exchange-Sort needs less exchanged than QuickSort.
I have to mention that exchanges aren't exchanges every time. I increment the counter, too, when an element is moved (for example in Insertionsort).
Exchanges should be atleast twice as costly as comparisons. Moves are really only an exchange/2.
I find an error of +/- 16ms when making several consecutive runs.
It happens, when your program calls DialogBoxParam.
When I trace, from where your program calls that API function,
this is where I go, and it never returns from the call to that API:
Should it really be DialogBoxParam? I can't image that. It means that I pass an invalid argument?
Could you please try whether this version starts ok (the display window won't work, this intended)?
Originally posted by bitRAKE
I find an error of +/- 16ms when making several consecutive runs.
I find an error of +/- 16ms when making several consecutive runs.
I already noticed that. I think that's because of task switching or do you have another thought?
Regards, Marwin
Could you please try whether this version starts ok (the display window won't work, this intended)?
What exactly do you mean, you haven't attached anything :confused: