🚀 go-pugleaf

> As long as we are comparing all of the sorting algorithms, how about
> shell sort?  Robert Sedgewick's "Algorithms in C" calls it "the method of
> choice for many sorting applications" and further states "In short, if you
> a sorting problem, use the above program [shell sort], then determine whether
> the extra effort required to replace it with a sophisticated method will be
> worthwhile."
> 
> I've ran comparisons for bubble sort, insertion sort, merge sort, quicksort,
> selection sort, and shellsort (assuming 8 compares = 4 moves = one function
> call) and Shellsort outperformed all of the other sorting routines on the
> average.  I tried sizes from 50 to 500000 elements, and I varied the
> percentage sorted between 0 and 100 percent.  When the data was really
> scrambled, quicksort was only slightly faster.  When the data was really
> ordered, shellsort was always first. Try it.  You'll love it.  And best
> of all, "no one has been able to analyze the algorithm" [Sedgewick - page 110].

I wholeheartedly agree here.  The shell sort has performed marvelously for me
in just about any use.  The programs I write for the Unit are mostly sorting,
and I have sorted files ranging from 15 to over 2 million lines using multiple
keys and the shell sort has performed admirably, with the added plus of _not_
being a memory hog (not naming any specific sorts here nudge nudge, wink wink)

There have been times though, when memory use was NOT a constraint (HAH!) that
I have used just about every sorting method (with the notable exception of the
radix sort, too much complexity here) but I keep returning to the shell sort.
(how's that for a run on sentence)

The main reasons _I_ use the shell sort are:
  1) relatively fast.
  2) easy/fast to customize for a particular data set
  3) just about any moron* (even those who graduate from UofL) can figure
     out the algorithm.  * insert your favorite word for "bad programmer" here,
                           the main exception being the ones TEACHING the
                           programmers... sheesh!
  4) uses minimal memory -- especially when one works with this in mind.
     It is amazing what one can accomplish in that d*mn 64K data segment
     limit imposed by the 8088 series family when one really tries.

and most important

  5) Coding the thing from scratch won't totally fry one's brain when in a
     hurry ("I need this data analyzed... yesterday")

Kendall.

-- 

   Kendall Sears                   KRSEAR02@ULKYVX.bitnet
   Programmer                             ///
   Child Development Unit                /// Amiga
   Department of Pediatrics          \\\/// Currently running AmigaOS 2.04
   University of Louisville           \XX/ And Supporting Unix Sys V Rev 4.
---------------------------------------------------------------------------
"Numbness is bliss... I can't feel a thing." -me.