In a message dated 04-08-98, George White said to David Noon about Faster
Than A Snail On ...
Hi George,
DN>Insertion sort is faster than Shellsort?
GW>Yes. It depends on the amount of disturbance to the data set (the
GW>crossover point for data set size varies in inverse proportionality to
GW>the amount of disturbance), but for small disturbance (<2.5% elements
GW>displaced @ 250 elements) it is faster. I've tested shellsort (ssort()
GW>in SNIPPETS) against the fully tweaked quickersort (qsort() from
GW>SNIPPETS) and both have similar timings on already ordered data.
If the Shellsort in SNIPPETS is the one posted by Bill Birrell and Herman
Schonfeld then it is a sub-optimal parameterisation (i.e. crepe). Use an
instantiation of the one I posted in C_PlusPlus instead.
Insertion sort, as your tests have already shown, is unbeatable for already
ordered datasets. One pass, n-1 comparisons, no moves, job done!
GW>I need to do more work on my test harness before I post it. I know of
GW>some structural changes to make it postable, there is some poor codeing
GW>practise in there (but it's OK for the "quick & dirty" testing things
GW>out code it started out as).
You want to use my SWAP() macro, don't you? ... :-)
Regards
Dave

___
 * MR/2 2.25 #353 * You are the Senate.  You have the power to filibuster.
--- Maximus/2 3.01
---------------