zmacy67@doc.ic.ac.uk (Roger Attrill) (05/03/90)
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. Thanks. =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- | Roger C. Attrill | * * I don't think therefore I'm not * * | | zmacy67@doc.ic.ac.uk | More variations on a theme | | Imperial College | same time next week folks | =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
jtc@van-bc.UUCP (J.T. Conklin) (05/04/90)
[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
gordon@cs.tamu.edu (Dan Gordon) (05/06/90)
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