🚀 go-pugleaf

libh@Jane.UH.EDU wrote:
: In article <BxD5pt.DyI@news.cso.uiuc.edu>, jas37876@uxa.cso.uiuc.edu (John A. Slagel) writes:
: >kds@phy.duke.edu (Stokes Kevin) writes:
: >
: >   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).
: >
:>  In other words, if you're sorting n objects, QuickSort takes "on the Order
: >   of" n*log n steps, while bubble sort takes "on the order of" n*n steps.
: >
:   The bubble sort takes N! (# factorial) steps, rather than N*N steps.  A BIG
: difference. 

Good god. What a brilliant piece of work! ;)
Just FYI, it really is N*N. a Q&D proof. In worst case it will move an
item of data D1 one place, and if D1 is at the opposite end of the
list from where it should be it will take N passes.. So it has to
handle N items of data N times --> O(n^2).

: But as pointed out, the quicksort is the easiest to implement
: since it is in C libraries.  Why reinvent the wheel.  If that isn't
: quick

That isn't implementing it, thats useing it.  If the speed of sorting
matters, DON'T use the qsort from the libs. two reasons.
1) It is has a big overhead on comparisons.
2) Q-sort is no where near the best sort to use, and it has an
abominable worst case performace. O(n^2).

: enough then I would check out Knuth's 'Art of Programming' Vol. 3 since it is
: pretty much only about sorting.

Knuth is a good place to look. Pretty much the definative work, but
starting to get a little dated.

Michael