🚀 go-pugleaf

In article <6759@news.duke.edu> kds@phy.duke.edu (Stokes Kevin) writes:
>
>  I am well along in a new 3D game engine, and I need some advice
>about sorting algorthms.  My past game, Corncob 3D, used a bubble sort
>to sort all the objects from farthest to closest to the observer.
>  This method seemed ok, because in a flight simulator, the objects are
>generally very sparse, and from frame to frame, there should be few changes
>in the order of objects.
>  This new project has objects much closer to the observer, and I fear
>there may be significant changes in the list order between every sort.
>Which sorting algorthm is the most time efficient?
>                                              -Kevin


Congratulations on picking a great topic - the signal-to-noise ratio on this
question is rapidly approaching zero. Most of the replies have been content-
free, and what little content the others had was quite often incorrect.

First, note that the poser of the original question already knows more about
sorting than a lot of the responders.  He knows that a naive sorting method
(bubble sort) is quite often optimal for a particular data set.  Under the
original constraints he gives (few changes in order between frames, so the
input data set is very nearly sorted) it will be hard to beat bubble sort.

O.K., so let's look at the replies to date.   Most useful suggestion - look
in Knuth volume 3: Sorting & Searching. As for the comment about Knuth being
somewhat dated - most of the advances in sorting techniques are at least 30
years old, so you won't miss much if you don't look anywhere else!

Most typical usenet posting (the authorative dissemination of incorrect
information) - the claim that bubble sort is O(n!), not O(n^2).  You
really have to try hard to get a sort that has worse behaviour than O(n^2).
Off hand I can only think of one sorting method that is O(n!), and that is
"Inspection sort": Look at the data set. If it isn't sorted apply a random
shuffle, and look again.  Repeat until the data is sorted.

 Most practical sorting methods vary between O(n log n) and O(n^2), with the
variations coming in the best-case, average, and worst-case performance.
(Radix sort is O(n), but the constant of proportionality can be rather large,
and it only really works well if the values to be sorted are fairly evenly
distributed over a range that is easily determined before the sort commences).

Bubble sort (and close relatives like insertion sort) is O(n^n) in the average
(and in the worst case), but is O(n) if the data is already sorted.

Quicksort is O(n log n) on random data sets, but O(n^2) in the worst case.
Unfortunately most quicksort implementations exhibit worst-case performance
if the input data set is already sorted.

Heapsort is consistently O(n log n) for all data sets, but the constant of
proportionality is often significantly higher than that for quicksort.

So where does this leave us? It leaves us knowing the one great truth of sorting:

        There is no single `best' sorting method.  The choice
        of a good sorting algorithm is extremely data dependant.

It sounds to me as though the original poster is trying to find a way of sorting
3-dimensional objects in 3-space. Presumably this is for some kind of display of
the view from a particular point.  Doing this fast has been one of the major
challenges of computer graphics over the last twenty or so years.  If most of
the objects are static, (albeit possibly with a moving viewpoint), and the scene
consists mainly of objects with planar faces, BSP (Binary Space Partitioning)
trees quite often provide an adequate solution.  Beyond that really depends on
what the data is and how it is expected to vary over time.  If the original
poster would like to provide more information (I suggest using email) I might
be able to provide some more concrete suggestions.
-- 
John Francis                                 johnf@apollo.hp.com
with 9 cats to feed, I don't have time to think up a clever .sig