Re: Smart sorting algorithm ?

[achrist@easystreet.com]

Wes Groleau wrote:
> 
> > > The reason I'm asking is that I have a situation
> > > where deciding the order of two items is very slow.
> > >
> > > If the program determines that A < B  and later
> > > determines that B < C and stores this information,
> > > then if and when A ? C comes up, it can determine
> > > the answer from the stored information.
> >
> > Using, e.g., qsort, isn't it true that this should not happen?  If
> > you've compared A vs B and B vs C, then B is the pivot, and A and C
> > are on opposite sides of the pivot and won't get compared.
> 
> Interesting point.  On a test of 18 items,
> one sort took 42 compares.  

I calculate log2(factorial(18)) > 52.  If an algorithm determined 
the correct order based on 42 bits of information,  it eliminated
some comparisons based on the results of others.  

> Another test
> of 18 items took 76 compares.  

A less fortunate initial ordering.  The binary insertion sort
or the sorting network should always be close to log2(factorial(n)), 
ie average case and worst case pretty much the same.


> And a test
> of 36 items to 172 compares.  I've discarded
> detailed logs, but it seems to me I saw several
> times the same two items being compared.
> 

log2(factorial(36)) = 138.1

I guess that quicksort will repeat comparisons if there are duplicate
items in the set of items being sorted.  Or if the pivots are selected
as a median of three or such to make very bad choices of pivot less
likely, then some of the comparisons used to select the pivot may be
repeated while doing the partition.  

IAC, the problem of sorting when comparisons are expensive isn't too
much different from the general problem of sorting.  If you have data 
that has particular likely arrangements before sorting, you should 
use an algorithm that takes advantage of that.   You haven't said 
anything about whether you want to optimize best-case, worst-case, or
average case, or what's average.  

Good luck with it.


Al