🚀 go-pugleaf

In article <1992Nov8.012628.23338@menudo.uh.edu> libh@Jane.UH.EDU writes:
>In article <BxD5pt.DyI@news.cso.uiuc.edu>, jas37876@uxa.cso.uiuc.edu (John A. Slagel) 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.  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
>enough then I would check out Knuth's 'Art of Programming' Vol. 3 since it is
>pretty much only about sorting.

Ack!!! People, remember that bubble sort has a *worst* case time of
n!.  It can be quite fast if most things are sorted.

Also, remember that all this n! vs. n*log n stuff if the asymtotic
behavior of the algorithm.  Meaning, this is the way the time vs. n
curve "looks".  There are also constants that are associated with
these curves which may make a "poorer" algorithm (with respect to its
O-notation) much faster than a "better" algorithm, ON YOUR DATA SET.

For instance, size has a lot to do with things.  If n is small, it may
be better to use another algorithm.  An example of this is that many
quick sorts end up using an insertion or other sort in the depths of
the sort when they have divided the data set down to a sufficiently
small number of elements.

Another example.  There is an algorithm for multiplying large integers
together that is O(n^1.xxx) where xxx is something I can't remember.
The naive algorithm is O(n^2).  For any integer size less than
something like 256 bits, it's usually better to use the naive approach
because the "better" approach has a huge constant in front of it that
isn't shown in the O-notation.  At small values of n, the naive
approach is better, but crosses over at larger n as the n^2
characteristic swamps whatever constant the better algorithm has.

So, in summary, it's never a clear case of O(n*log n) is always better
than something O(n*n) or O(n!).  It really depends on what n is and
what sort of constants aren't shown in the O-notation for the "better"
algorithms.  It also depends on your data set.  Some things that are
O(n!) in the worst case degenerate down to something O(n) if you know
something about the data that is being operated on.

Dave Roberts
Advanced Micro Devices, Inc.
Network Products Division
david.roberts@amd.com