🚀 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?
and thus starts the sorting thread.


Sorting depends on the randomness of the data and the size of the data.
Furthermore,  how "good" a sorting algorithm really is depends on the
relative speeds of a compare operation, a move operation, and a function call.

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 used the NeXT computer's "SortingInAction" to run the comparisons.  It's
an excellent program (source provided), and can be found in the
/NeXTDevelopers/Examples directory.  As far as I'm concerned, I've never seen
a better way to experimentally test sorting algorithms, theoretical math be
hanged!)

=============================================================================
-Mike Kienenberger                       FXMLK@ALASKA           (BITNet)
 Academic Computing                      FXMLK@acad3.alaska.edu (Internet)
 University of Alaska-Fairbanks
 "I'm a computer programmer....<link><link><kludge><kludge> say-no-more!"