🚀 go-pugleaf

John A. Slagel (jas37876@uxa.cso.uiuc.edu) wrote:
: kds@phy.duke.edu (Stokes Kevin) writes:
: 
: 
: >  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?
: 
:    Definately the quick sort.  Its even built into ANSI C specs, so it
:    should be easy to implement.  Look up quicksort in your C manual. If
:    I remember right, bubble sort works in O(n*n) and quicksort works in
:    O(n*log n).

Wait a bit..
Quicksort is nothing like the best. It has an AVERAGE running time of
N log N,  but the worst case is n^2. The worst case occurs when the
data is already sorted.... Nearly sorted data does very badly. On top
of this, the quicksort is difficult to implement efficently.

If you want a real FAST sort, implement a merge sort, or a radix sort
(radix is O(n), but it is only useful for small numbers). Merge has a
worst case of N log N, but needs more memory than a quicksort. On the
up side, it can be made very fast.
 
:   John A. Slagel, email: jas37876@uxa.cso.uiuc.edu
Michael