Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!ucsd!ucbvax!van-bc!jtc
From: jtc@van-bc.UUCP (J.T. Conklin)
Newsgroups: comp.graphics
Subject: Re: all sorts
Keywords: sorts, shell-metner
Message-ID: <374@van-bc.UUCP>
Date: 4 May 90 02:51:18 GMT
References: <1857@gould.doc.ic.ac.uk>
Reply-To: jtc@van-bc.UUCP (J.T. Conklin)
Followup-To: comp.misc
Distribution: comp.graphics
Organization: UniFax Communications Inc., Vancouver, B.C., Canada
Lines: 60

[Followup-To: comp.misc]

In article <1857@gould.doc.ic.ac.uk> zmacy67@doc.ic.ac.uk (Roger Attrill) writes:
>  I am currently writing a 3-D solids modeller.  A simple part of this
>requires the depth sorting of a large number of triangular surfaces. While
>the quicksort algorithm is ok, I have heard of the Shell-Metzner sort,
>(actual spelling unknown). I have even spoken to two other people who
>have heard of it, but I can't find anyone who has GOT it. If any one knows
>the algorithm, or knows someone who knows someone .....   then I'd be very
>grateful. Also If anyone knows any other very fast sorting algorithms ( ie 
>faster than quicksort ) then I'd like to hear from you.

You really need to grab an elementary algorithms text before you start
evaluating the performance of sorting algorithms.  I suggest taking a 
look at Knuth's Sorting and Searching.

That said, every algorithm has its strengths and weaknesses.  The data
that you are working with will play a large part of which algoritm you
choose.

For example, the ubiquous bubblesort.  It is small, easy to implement,
and quite slow O(n^2).  But if you are only sorting a few elements, it
may be faster than a more complex algorithm with higher overhead.

Quicksort is is generally quite fast O(n log n), but its worst case
behavior (a pre-sorted list) is O(n^2).  If your list tends to stay
sorted, a you might choose other O(n log n) algorithms like heapsort
or mergesort.

The Shell sort tends to fall between the fast algorithms like
quicksort, and the slow ones like bubble sort.  I believe it is
O(n^1.5).  It goes something like this:

    procedure ShellSort(var A: array[1..n] of integer);

    var
       i, j, incr: integer;

     begin
       incr := n div 2;
       while incr > 0 do begin
         for i := incr+1 to n do begin
           j := i-incr;
           while j > 0 do 
             if A[j] > A[j+incr] then begin
               swap(A[j], A[j+incr]);
               j := j - incr;
             end
	     else
               j := 0;
         end;
         incr := incr div 2;
       end;
     end;

     --jtc

-- 
J.T. Conklin	UniFax Communications Inc.
		...!{uunet,ubc-cs}!van-bc!jtc, jtc@wimsey.bc.ca