Sorting algorithms benchmark

Stewart Gordon smjg_1998 at yahoo.com
Wed Feb 28 17:58:41 PST 2007


Deewiant Wrote:

<snip>
> Your comb sort uses a shrink factor of 0.7.  Comb sort 11 uses 
> 1 / (1 - 1 / (e ^ phi)), where e is Napier's constant and phi 
> the golden ratio.  This leads to possible optimization in the 
> algorithm.

Hang on - isn't 0.7 a grow factor, rather than a shrink factor?

<snip>
> You're missing shell sort: 
> http://en.wikipedia.org/wiki/Shell_sort

Indeed, that could be implemented as well.

I noticed there:
"For instance, if a list was 5-sorted and then 3-sorted, the 
list is now not only 3-sorted, but both 5- and 3-sorted."
Guess I should read up on the proof sometime.

<snip>
> Other sorts that could be added:
> 	- Gnome sort, http://en.wikipedia.org/wiki/Gnome_sort

Not sure if this one is worth it....

> 	- Introspective sort: http://en.wikipedia.org/wiki/Introsort
> 	- Three-way merge sort:
> http://www.cs.queensu.ca/home/cisc121/2002w/assignments/assn8/solution/MergeThreeWay.java

Certainly worth considering.

> 	- Counting sort, http://en.wikipedia.org/wiki/Counting_sort
> 	- Bucket sort, http://en.wikipedia.org/wiki/Bucket_sort
> 	- Pigeonhole sort, 
> http://en.wikipedia.org/wiki/Pigeonhole_sort
<snip>

It took me a moment to figure the difference between these three.  But I would need to reduce the range of the random sequences a lot before any of them will be remotely feasible.

Stewart.



More information about the Digitalmars-d-announce mailing list