Path: utzoo!attcan!ncrcan!becker!censor!comspec!tvcent!lethe!torsqnt!news-server.csri.toronto.edu!cs.utexas.edu!helios!gordon
From: gordon@cs.tamu.edu (Dan Gordon)
Newsgroups: comp.graphics
Subject: Re: all sorts
Keywords: sorts, shell-metner
Message-ID: <5234@helios.TAMU.EDU>
Date: 6 May 90 16:07:50 GMT
References: <1857@gould.doc.ic.ac.uk> <374@van-bc.UUCP>
Sender: usenet@helios.TAMU.EDU
Organization: Computer Science Department, Texas A&M University
Lines: 42

In article <374@van-bc.UUCP> jtc@van-bc.UUCP (J.T. Conklin) writes:
>[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.
]
]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,
   
]Quicksort is is generally quite fast O(n log n), but its worst case
   
]or mergesort.
  
]The Shell sort tends to fall between the fast algorithms like
  
		-- stuff deleted --
  
If you want to do depth sorting, your best bet is bucket sorting. For every
integral value of z between ZMIN and ZMAX, maintain a sorted linked list of
all the points whose integral value of z matches the bucket number. At the
end, you can copy all the points from the lists into an array and get a
sorted array of the points. Alternatively, you can link the lists together
to form one sorted linked list of all the points. If you want this second
alternative, then it is more efficient to maintain a pointer to the end of
each list. See any good book on data structures and/or design & analysis of
algorithms.

Let us all know what works best for you. There are papers in computational
geometry that indicate that bucketing techniques work best in practice, even
though their theoretical worst-case running times are bad.

Dan Gordon