Author: Ricardo Gibert
Date: 18:25:16 10/18/99
Go up one level in this thread
On October 18, 1999 at 21:15:52, Dann Corbit wrote: >On October 18, 1999 at 20:39:26, Ricardo Gibert wrote: >>On October 18, 1999 at 13:49:26, Dann Corbit wrote: >> >>>On October 17, 1999 at 17:07:30, Ricardo Gibert wrote: >>>[snip] >>>>>And bubblesort has the advantage of being the best algorithm to sort already >>>>>ordered lists. >>>> >>>>Shaker sort does this faster. >>>Linear insertion is also faster and binary insertion even faster. Quick sort >>>with Singleton's modification should not be used for partitions smaller than 20 >>>elements. >> >>"Quick sort with Singleton's modification" sounds a little like a couple of >>algorithms I've come up with for this task. Could you give a brief description? > >Quicksort with Richard Singleton's modification was invented in 1968 by R. C. >Singleton. He produced the following improvements for the quick sort algorithm >by Hoare: >0. When the partition size is smaller than "threshold" use insertion sort. >Singleton suggested 10 for threshhold. >1. Use a median of three elements to choose the pivot >2. Instead of a recursive implementation, an interative version was provided. > >It is called in the literature "ACM Algorithm 347" This all looks familiar, except I did not know this was called Singleton's modification. I was thinking of something quite different. Thanks though.
This page took 0.01 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.