In a message dated 04-16-98, Mathieu Bouchard said to David Noon about Sort
Algorithm
Hi Mathieu,
MB>I expected more than this :-) the idea is old news for me. I didn't
MB>know quickersort was just that. That kind of improvement can be done on
MB>lots of sorts. I usually use bubblesort for that kind of thing. :-)
This is not the end of the improvements for Quicksort though.
MB>there are probably lots of more optimal versions of this now, i guess.
In this QWK packet I'll be uploading a Quicksort template that incorporates
the median-of-three pivot selection, which also improves performance quite
measurably.
MB>i found a version that doesn't really "exchange"; i found it was faster
MB>on completely random arrays, but not that good elsewhere; there could
MB>be improvements on the top of it that could make it better in most
MB>useful cases than the classic quickersort.
Yes. Early next week I will be posting a version with the recursive calls
removed, on top of the other refinements.
If you have been looking at the various Quicksort templates I've posted of
the last few weeks you will have seen the evolution of the algorithm from
Hoare's original paper at the beginning of the 1960's through to Sedgewick's
Ph.D. thesis that removed recursion.
So, watch this space. ... :-)
Regards
Dave

___
 * MR/2 2.25 #353 * User-friendly: (adj.) trivialized, slow, incapable, and 
boring.
--- Maximus/2 3.01
---------------