🚀 go-pugleaf

    Russ Trotter entitled a message as 'Re: advice needed for fas',
   on the 11-11-92  16:10 to All.
 RT> I hate to jump on this seemingly runaway train but.... 

 RT> In one of my classes, I remember the teacher saying that it
 RT> had been proven that O(n log n) was the best one could do
 RT> for _comparison_ based sorting...  Is this a more correct assertion?

 RT> I don't know much (at all :) ) about Radix sort  (only how to spell it
 RT> :) ) so I can't be sure if it disproves the statement above.


 RT> I've seen posts flying back and forth about this and quite frankly
 RT> I'm getting a bit confused...

    Let me help SORT this out.  Basically some algorythmes are
    faster at different sort sizes.  This is because O() notation
    ignores constants IE minimume setup/execution times.
    therefore lets say we were sorting a 12 item array.

    Lets say Quick sort ACTUAL speed is
    36.43*(n log n)
    and bubble sort is
    5.75*(n*n)

    for 12 items the bubble sort comes out around
    829

    quick sort would come out
    1089

    now which one is faster?

    Quick sort is recursive.  This means though it may have the
    fewest comparisons it also has to contend with stack
    overhead.  Each new partition requires 2 new pointers be
    allocated on the stack PLUS any local data.  This ussually
    takes a LOT longer than a comparison (unless sorting
    strings).  In this case we are dealing with numerical data
    and a comparison here is much quicker than the added stack
    operations.

    There are a number of criteria that must be specified in a time
    critical application before using a particular algorythm.

    Here are some I've pointed out.

    how many comparisons and how long is each comparison?
    how many recursions and local data operations?
    how long does it take to "move" data? (swaping pointers or
        swaping values)
    
    these must be all relative to the NUMBER of items sorted.  In
    some cases there will be a large difference.  In others there
    will be virtually none.

    In this persons case he want a VERY fast algorythm and likely
    for no more than 20 items.  This is also frequently sorted
    data so it is very likely to be nearly sorted already.  All
    of these hint at using a simpler sort that can check for
    everything being sorted before going into coniptions.  I'm
    not sure if Qsort does this (been a while since I've needed
    to sort things).

                Stephen Cyberman@Toz.Buffalo.NY.US
             Mangled on Thu  11-12-1992  at 20:25:15

... This tagline is not taxed ,... YET !
--- Blue Wave/QWK v2.10