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