🚀 go-pugleaf

In article <1dj6jmINNder@tartarus.uwa.edu.au>, oreillym@tartarus.uwa.edu.au (Michael O'Reilly) writes:
|> 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
	Not only has quicksort bad worst-case performance, but this worst 
case WILL occur in the considered application, since the list will always be
nearly sorted after any reasonable wievpoint movement.