Sort Algorythm

[Infro_X]

Attached is my sort algorythm that i tried to create. I was wondering how it compares to others you guys have made. Please give me your opinions, and bugs if you see any. Thanks. (tring, possibly hopelessly to beet the quicksort algo)

[attachment deleted by admin]

[pbrennick]

Hi Infro_X
I have not had a chance to try your sort as of yet but I noticed that you included the original C++ stuff in the comments.  This makes a good tutorial on how to convert from 'C++' to .ASM.  Because of this, I converted the project to MASM32 syntax so that everyone can benefit from it.  :thumbu :thumbu

Paul


[attachment deleted by admin]

[Infro_X]

Thanks pbrennick, perhaps now i can get some feedback, hehe. anyhow it'd be quite nice if it helped anyone converting to C++ to ASM.

[pbrennick]

How do you use it?

Paul

[raymond]

A brief description of what it is intended to do would have been nice :wink
along any restrictions it may be expected to have.

Raymond

[Infro_X]

infrosort base:DWORD,size:DWORD

base is the base address of the array you want to sort (only does dWords currently), size is the size in bytes of array, its a sorting algorythm, i included a pseudo random number generator with it to create a DWORD array of random numbers, then to sort them. if you open it up in olly DBG you can go to the infro sort proc, and look at the memmory offset stored in edi or the first pushed param, [esp+4].

Simply put, it sorts numerically a bunch of numbers. Attempting to beat the speed of the quick sort algorythm, or at the very least, come withing competetive range.

[hutch--]

Infro,

You have little chance of producing a faster algo that a quick sort if the data you are sorting is close to random in its distribution. Where a quick sort falls over is if the data is near ordered or if the range is very limited. You can improve this by a number of devices, usually changing the pivot position but each addition makes a quick sort slower.

A useful approach is to think in terms of hybrid sorts, a quick sort that delegates small parts of its task to an "insertion" sort is one approach that is usually successful.

A year or so ago I did a lot of work on string sorts that did the comparisons directly inline to cut down on the call overhead and the fastest was a quick sort that was completely unprotected on true random data. The same quick sort would fail due to excess recursion depth on presorted data or data that did not have much range (a million items with a numeric range of 1 to 10) for example.

I produced another variation of what is called a "comb" sort where I used that algo only as a pre-ordering phase and cleaned up the rest with an insertion sort and it times reasonably well but its big gain is that I could not find a data ordering that would force it into quadratic timings.

The final version I settled on was a leading quick sort with a recursion depth indicator that exited if the depth was too deep and it fell back to the hybrid comb/insertion sort. The algos are in the MASM32 library and there is some documentation in the masmlib help file.

[whiteknight]

if i remember correctly, the microsoft libc implementation of qsort is a hybrid sort with a quicksort front end, that converts to a bi-directional bubblesort for sublists of 8 entries or less. i might have some of the details confused.

[Eóin]

When I implemented my own sort routine I used a hybrid qsort/bubblesort which I got from here. I'll post the code later if I get a chance.

However what I think might be more interesting to study is a recent algorithim, Introspective Sort (PS, PDF). Its already replaced quicksort in SGI's STL implementation. To quote them-

"Earlier versions of sort used the quicksort algorithm (C. A. R. Hoare, Comp. J. 5, 1962), using a pivot chosen by median of three (R. C. Singleton, CACM 12, 1969). Quicksort has O(N log(N)) average complexity, but quadratic worst-case complexity. See section 5.2.2 of Knuth for a discussion. (D. E. Knuth, The Art of Computer Programming. Volume 3: Sorting and Searching. Addison-Wesley, 1975.) The current implementation of sort, however, uses the introsort algorithm (D. R. Musser, "Introspective Sorting and Selection Algorithms", Software Practice and Experience 27(8):983, 1997.) whose worst case complexity is O(N log(N)). Introsort is very similar to median-of-three quicksort, and is at least as fast as quicksort on average."

[roticv]

Any idea what's the average case?

[Eóin]

roticv Was that question directed at my post about IntroSort? If so then unfortunatly I havn't read the paper in detail so I don't know. My initial thoughts would be that both QuickSort and IntroSort have O(N log(N)) average case, but while QuickSort degrades to O(N²) in worst case, IntroSort doesn't.

Here's the code I promised, unfortunatly its FASM code and also unfortunatly its part of a generic data structres and algos library I'd wanted to build so the demo program will be hard to compile. (Anyone who'd be interested in getting it to work should contact me and I'll send on any extra files needed :) )

That said the two QuickSorts are independant asm files and should be easy to convert to MASM. The plain QuickSort sorts unsigned 32bit integers in a linear array. The QuickSortFun also operates on 32bit dwords in a linear array, but you provide the comparasion function as a callback and so the dwords can be integers, real32s or even pointers to complicated objects.

The program (Win32.exe) should run, it'll take a few seconds to appear cause it times itself sorting 10,000,000 integers before displaying. If someone manages to recompile it use the QuickSortFun you'll see its about 3 times slower. Heres the output of plain QuickSort on my 2.4Ghz P4.

QuickSort
Array of 10000000 initialised
Start timing at 4864214
End timing at 4865646, Total 1432


[attachment deleted by admin]

[hutch--]

I played with bi-directional bubble sorts to handle the tail end of other partial sorts but the insertion sort was far faster than the bi-directional or "cocktail shaker" sort with near ordered data. With Quick Sorts, a fully unprotected quick sort is still the fastest on randomly distributed data but as soon as you start adding tri-median code to extend its range on oddly or partially ordered data, its gets noticable slower.

I found it more useful to run it with a recursion depth indicator and when it exceeded a preset depth, dump it and use an alternative.

The alternative was a combination of different sort designs, a COMB sort is a reasonably reliable design which is a derivation of a bubble sort but it had a similar weakness with values at the wrong end of the array so I ran the COMB sort bi-directional to solve this problem. A COMB sort collapses into a bubble sort when the gap reduces to zero and its here where it is not fast enough. I substituted an insertion sort to handle the end of the COMB preordering stage and it ended up a lot faster.

The win with this design is its predictability, the COMB pre-ordering stage has a finite and predictable number of passes before the gap reduces to zero then pass it to an insertion sort to clean up the near ordered data into fully ordered. By it being predictable in duration its very hard to feed anything to it that will lock it up or force it into quadratic timings. While I don't know of a way to prove this result, it easily handles deliberately ordered data that will kill others stone dead.

With for example a million items to sort, if they are all the same value, if they are sorted in either direction and with a very good test that Jibz designed with reverse sorted data alternately spaced it runs in predictable times with no quadratic collapses. I plugged the fastest version of the quick sort at the front of it with a recursion depth indicator to handle highly random data.