In a message dated 04-03-98, George White said to David Noon about Qsort-ing
A Struct
Hi George,
GW>Or pages 106 to 111 of Knuth, Vol 3, first edition.
Thanks. Saves me digging out my copy just yet.
GW>Knuth's comment (page 110): "Compared to straight insertion (Algoritm
GW>5.2.1S), bubble sorting requires a more complicated program and takes
GW>about twice as long!"
I knew I didn't make up the bit about 2:1 speed ratio.
DN>I always benchmark algorithms using the same test datasets.
GW>Me too :-)
The only sensible way to benchmark.
DN>Neither would I. I would not use them for more than 8.
GW>Seconded (though maybe I'd go up to 10 items).
Mileage varies with the type of data being sorted and the suitability of the
CPU used. For character strings on an Intel I would stick with 8, but
doubles, as I used above, would likely be Ok up to 10.
GW>My test timings were instructive. With all the speed ups a quickersort
GW>is faster than shellsort except where the data is close to ordered, and
GW>even then it isn't too far behind. Your code as posted in the template
GW>in C_Plusplus would be very slow on close to ordered data because the
GW>test key you use brings it back to N^2 time.
Yes, that's a known defect in Hoare's algorithm. It prefers a mess to almost
ordered data.
GW>Using R. C. Singleton's
GW>method of selecting the median of the left, right and center elements as
GW>test key improves peformance significantly in this case (and improves it
GW>in general as well ).
Watch C_PlusPlus for a new template soon.
Regards
Dave

___
 * MR/2 2.25 #353 * If this was funny it would be a tagline.
--- Maximus/2 3.01
---------------