Sign in to follow this  
Followers 0
Nutster

Sorting Functions

13 posts in this topic

#1 ·  Posted (edited)

Here is a set of sorting routines. You would typically only use one and leave the others behind. I went looking for ones I posted on the Yahoo! group a few years ago, but could not find them, so I recreated them from scratch :) . These all have the standard UDF headers on them and I guess I could split them up into multiple files to make it easier for people use them one at a time. Let me know if there interest.

Some notes on these sorts:

  • All the sorts are of the comparison variety. Other types are less practical when the internal datatype could be string or numeric.
  • All sorts are pure, that is, each sort is one type without handing off to another type of sort as things change. There are several optimizations available if one type of sort passes off to another under different circumstances.
  • Even optimized as it is, the bubble sort is the smallest and slowest O(n²) sort. :P
  • There are two insertion sorts. One uses a binary search to speed things up, instead of a linear search, but the overhead of binary search slows it down for smaller arrays.
  • The shell sort is generally the fastest of the O(n²) sorts I put in this set and the hash sort is the slowest of the O(n log n) sorts.
  • This quick sort picks its pivot from the middle of the sub-array to be sorted, thus transforming the in-order worst-case scenario that quick sort can suffer from into actually its near best-case scenario.
  • There are some poor sorts, worse than O(n²), in the Sorts.au3 file. They are mainly there as examples. They are not currently selected in the testing script, but can be added easily.
  • The testing script runs the sorts generally in order from slowest to fastest, comparing the speeds of each sort for the same random number set.
  • The testing script has lines near the beginning that can be un-commented to perform certain same-value, in-order and reverse-order testing.
  • If you want to try the poor sorts, keep the number of elements small or you will be waiting a really long time.
  • If you want to test a lot of elements, take out the sorts up to Gnome sort or even Comb sort to save time.

Comments are welcome.

Sorts.au3

Sorts_Test.au3

Edited by Nutster

David Nuttall
Nuttall Computer Consulting

An Aquarius born during the Age of Aquarius

AutoIt allows me to re-invent the wheel so much faster.

I'm off to write a wizard, a wonderful wizard of odd...

Share this post


Link to post
Share on other sites



No monkey sort?

That was always my favorite sort.


Share this post


Link to post
Share on other sites

No monkey sort?

That was always my favorite sort.

I am not familiar with that one and my research did not show that one. How does that one work?

David Nuttall
Nuttall Computer Consulting

An Aquarius born during the Age of Aquarius

AutoIt allows me to re-invent the wheel so much faster.

I'm off to write a wizard, a wonderful wizard of odd...

Share this post


Link to post
Share on other sites

Ah, I see I am a fool. In my cursory glance at the algorithms I didn't realize that the bozo sort was just a different name for a monkey sort. Theres nothing quite as beautiful as a sort that runs in O(n!). I think the name comes from the fact that its so easy even a monkey could do it.


Share this post


Link to post
Share on other sites

#5 ·  Posted (edited)

Hi,

I like this!;

Are you interested to add the vbs called and jscript called sorts?;

jscript wins easily for numeric, and vbscript starts to fire over about 600 elements; [PS the fastest returns a delimited string; I don't think there is away of doing that in jscript to return through scripting object, else it would be faster than just 2-3x, as shown... (at present, I have to stringsplit from within AutoIt, which is relatively slow)]

Best, Randall

[i have moved these funcs, rewritten to old 1D thread;]

Array sort in scriptcontrol8-10x faster

Edited by randallc

Share this post


Link to post
Share on other sites

#6 ·  Posted (edited)

Again, jscript for string sorting becomes more than an order of magnitude faster;

Sort Test ;

Relative Timings (ms) on 10000 elements:

AutoIt Sort: 3800

Merge Sort: 4176

Array2D1DFieldSortSt Sort: 890

JSort1DStr Sort: 224

JSort1DaStr Sort: 164

Shell Sort: 3408

Quick Sort: 3142

Sort Test ;

Speed Rel AutoIt Sort: 10000 elements:

AutoIt Speed Rel AutoIt Sort: 1

Merge Speed Rel AutoIt Sort: 0.91

Array2D1DFieldSortSt Speed Rel AutoIt Sort: 4.27

JSort1DStr Speed Rel AutoIt Sort: 16.96

JSort1DaStr Speed Rel AutoIt Sort: 23.17

Shell Speed Rel AutoIt Sort: 1.12

Quick Speed Rel AutoIt Sort: 1.21

and we should include the pure AutoIt fastest, "IntroSort" by _Ultima_?

Sort Test ;
Relative Timings (ms) on Strings: 1000 elements:
AutoIt Sort: 400
IntroSort Sort: 207
Array2D1DFieldSortSt Sort: 131
JSort1DStr Sort: 49
JSort1DaStr Sort: 20
Shell Sort: 239
Quick Sort: 262

Sort Test ;
 Speed Rel AutoIt Sort: Strings: 1000 elements:
AutoIt Speed Rel AutoIt Sort: 1
IntroSort Speed Rel AutoIt Sort: 1.93
Array2D1DFieldSortSt Speed Rel AutoIt Sort: 3.05
JSort1DStr Speed Rel AutoIt Sort: 8.16
JSort1DaStr Speed Rel AutoIt Sort: 20
Shell Speed Rel AutoIt Sort: 1.67
Quick Speed Rel AutoIt Sort: 1.53

Sort Test ;
Relative Timings (ms) on Numbers: 1000 elements:
AutoIt Sort: 274
IntroSort Sort: 145
Array2D1DFieldSortSt Sort: 114
JSort1D Sort: 66
JSort1Da Sort: 61
Shell Sort: 207
Quick Sort: 232

Sort Test ;
 Speed Rel AutoIt Sort: Numbers: 1000 elements:
AutoIt Speed Rel AutoIt Sort: 1
IntroSort Speed Rel AutoIt Sort: 1.89
Array2D1DFieldSortSt Speed Rel AutoIt Sort: 2.4
JSort1D Speed Rel AutoIt Sort: 4.15
JSort1Da Speed Rel AutoIt Sort: 4.49
Shell Speed Rel AutoIt Sort: 1.32
Quick Speed Rel AutoIt Sort: 1.18

[i have moved these funcs, rewritten to old 1D thread;]

Array sort in scriptcontrol8-10x faster

Edited by randallc

Share this post


Link to post
Share on other sites

#7 ·  Posted (edited)

@Nutster: Nice stuff. Although I do fiddle with sorting functions occasionally myself, I've always held a slight dislike for implementing them (even if some of them are easy to implement -- don't ask why, because I don't know either xD). For that reason, I commend you for implementing so many of them :)

Edited by -Ultima-

[ WinINet.au3 | Array.au3 (Optimized) | _UnixTimeParse() ]

Share this post


Link to post
Share on other sites

I have updated the sorts to be in multiple files with only the functions they need. See the attachment. I also added a comparison to _ArraySort, which uses a combination of quick sort and insertion sort. Again, I did not include hybrid sorts (other than _ArraySort) or sorts that rely on calls to other languages.

Sorts_2.zip


David Nuttall
Nuttall Computer Consulting

An Aquarius born during the Age of Aquarius

AutoIt allows me to re-invent the wheel so much faster.

I'm off to write a wizard, a wonderful wizard of odd...

Share this post


Link to post
Share on other sites

I have updated the sorts to be in multiple files with only the functions they need. See the attachment. I also added a comparison to _ArraySort, which uses a combination of quick sort and insertion sort. Again, I did not include hybrid sorts (other than _ArraySort) or sorts that rely on calls to other languages.

Hi,

Interesting. I will move my demos to a new thread when I get time; it looks as though you want to keep this thread as a demo for pure programming technique rather than to look at utilty aspects.. if I understand correctly.

I am still trying to stimulate interest in getting a Sort for AutoIt which actually packs some more speed; a Dll call to a C script or similar; you don't know of any, by chance?

best, randall

Share this post


Link to post
Share on other sites

Hi,

Interesting. I will move my demos to a new thread when I get time; it looks as though you want to keep this thread as a demo for pure programming technique rather than to look at utility aspects.. if I understand correctly.

I am still trying to stimulate interest in getting a Sort for AutoIt which actually packs some more speed; a Dll call to a C script or similar; you don't know of any, by chance?

best, randall

Hello,

Part of my point for doing this was how to do the sorts in AutoIt, primarily as a challenge to myself to see if I could do it. I posted them because I thought others might find it useful. As for your proposals, I do realize there is utility in hybrid sorts, like IntroSort or the already implemented _ArraySort, which can be much faster by using different sorting algorithms for different circumstances. This just wasn't my focus.

Also switching to VBS or Javascript to do the work was not my focus either. I wanted these to be AutoIt sorts. Besides, my VBS is not strong enough for something like this and I prefer to use Javascript only for web pages. I could have written the sorts in C, compiled them into a DLL and called them using FileInstall and DLLCall, and these would be way faster than something written natively in AutoIt, but again that would miss my point. Besides, I have AutoIt on my Dad's computer, where I am visiting for the holidays; I do not have a C-compiler on it.

Strictly speaking, IntroSort uses only QuickSort and switches to heap sort if the recursion gets too deep; I have not seen an implementation that dumps out to insertion sort like that for small lists before. It is probably faster than a standard IntroSort. Interesting.

Still looking at the IntroSort, I noticed a Median of Three method for finding the pivot. This method can be tripped up by certain sequences that can get your sort locked up in recursive infinite loops. However, if this does start going crazy, the recursion trap should break it out of it into heap sort.

As for speed, the ShellSort and QuickSort implementations are quite fast, even coded in AutoIt. Look at the comparisons in the testing script in the .ZIP file.

BTW, when you are going to insert your code in something somebody else wrote and then distribute it, please comment on what you added or changed. Just by reading the coding style change, it is clear somebody else wrote a huge chunk, but who is responsible for problems or questions? Not me! It probably would have been better to put your stuff in a separate file and #include it where it would be used.


David Nuttall
Nuttall Computer Consulting

An Aquarius born during the Age of Aquarius

AutoIt allows me to re-invent the wheel so much faster.

I'm off to write a wizard, a wonderful wizard of odd...

Share this post


Link to post
Share on other sites

Hi,

Thanks for that; points taken, and i will do;

Best, randall

[PS - When you get the chance, I think AutoIt could benefit from faster sort... if you can do DLL from C.... and really want a suggetsion for a project!? I have only done "Hello World" in C, and not sure if the C compiler in a VMWare install is still on my computers either...]

Share this post


Link to post
Share on other sites

My C / C++ compiler is at home. I go back Sunday afternoon. Unfortunately, I am going back to a rather full schedule for a few days, so building a sort DLL is low-priority. Try the _ArraySort() UDF; it seems pretty fast for one-dimensional sorting and it has an option for 2-dimensional sorting (I did not test that though).


David Nuttall
Nuttall Computer Consulting

An Aquarius born during the Age of Aquarius

AutoIt allows me to re-invent the wheel so much faster.

I'm off to write a wizard, a wonderful wizard of odd...

Share this post


Link to post
Share on other sites

Strictly speaking, IntroSort uses only QuickSort and switches to heap sort if the recursion gets too deep; I have not seen an implementation that dumps out to insertion sort like that for small lists before. It is probably faster than a standard IntroSort. Interesting.

Hi,

Yes,

I looked up IntroSort a little at the time Ultima posted them, and took a long time to convert the AutoIt to vbs, so was surprised to find it did not seem to help the speed in vbs vs QuickSort!

It seemed, from reading, that performance was affected a lot by the program environment/ language used, but it seems good in AutoIt!

Best, Randall

[PS I have changed those UDFs and movd them as edited in previous posts]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0