Smart sorting algorithm ?

Smart sorting algorithm ?

[Wes Groleau]

Anyone know anything about a sorting algorithm
that includes the ability to infer the answer
to a comparison from comparisons already done?

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.

I have ideas for two ways to do this, but
if it's already been done.....

I know this is not the best newsgroup for the topic,
and I will ask elsewhere, but if I find an Ada solution,
it's that much better.

-- 
Wes Groleau
http://freepages.rootsweb.com/~wgroleau

Re: Smart sorting algorithm ?

[achrist]

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.   


Al

Re: Smart sorting algorithm ?

[Wilhelm Spickermann]

--Am Dienstag, Juli 02, 2002 11:32:01 -0500 schrieb Wes Groleau 
<wesgroleau@despammed.com>:

>
> Anyone know anything about a sorting algorithm
> that includes the ability to infer the answer
> to a comparison from comparisons already done?
>
> 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.
>
> I have ideas for two ways to do this, but
> if it's already been done.....
>

Hi,

have a look into D.E.Knuth: The Art of Computer Programming, Vol 
3: Sorting and Searching. Subsection 5.3.1: Minimum Comparison 
Sorting.

Wilhelm

Re: Smart sorting algorithm ?

[Gautier direct_replies_not_read]

>Anyone know anything about a sorting algorithm
>that includes the ability to infer the answer
>to a comparison from comparisons already done?

Here are 3.5 algorithms (here for sorting faces of
3D objects)

  http://www.mysunrise.ch/users/gdm/e3d_html/eng3dsor__adb.htm

You can also try to re-use a whole previous sorting,
in some situations it helps a lot.

HTH
____________________________________________________________
Gautier  --  http://www.mysunrise.ch/users/gdm/index.htm#Ada

NB: For a direct answer, address on the Web site!


_________________________________________________________________
Send and receive Hotmail on your mobile device: http://mobile.msn.com

Re: Smart sorting algorithm ?

[Florian Weimer]

Wes Groleau <wesgroleau@despammed.com> writes:

> The reason I'm asking is that I have a situation
> where deciding the order of two items is very slow.

Try insertion sort with a binary search.  Still O(n^2) operations in
total, but only about log_2 n! comparisons.

Re: Smart sorting algorithm ?

[Wes Groleau]

> > 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.  Another test
of 18 items took 76 compares.  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.

This is a variation of quicksort where only one
of the two slices is recursive.  Author claims
it saves a heck of a lot of memory.  I don't really
care about memory, but it was the first open
source Ada sort in my search results.

-- 
Wes Groleau
http://freepages.rootsweb.com/~wgroleau

Re: Smart sorting algorithm ?

[Wes Groleau]

> have a look into D.E.Knuth: The Art of Computer Programming, Vol
> 3: Sorting and Searching. Subsection 5.3.1: Minimum Comparison
> Sorting.

Thanks, I will do that if I can find it.
(I got volume one at a garage sale, and
I've never seen any of the others anywhere.)

-- 
Wes Groleau
http://freepages.rootsweb.com/~wgroleau

Re: Smart sorting algorithm ?

[Wes Groleau]

> > The reason I'm asking is that I have a situation
> > where deciding the order of two items is very slow.
> 
> Try insertion sort with a binary search.  Still O(n^2) operations in
> total, but only about log_2 n! comparisons.

Excellent idea!  Thanks!

-- 
Wes Groleau
http://freepages.rootsweb.com/~wgroleau

Re: Smart sorting algorithm ?

[Tarjei T. Jensen]

Wes Groleau wrote:
> > have a look into D.E.Knuth: The Art of Computer Programming, Vol
> > 3: Sorting and Searching. Subsection 5.3.1: Minimum Comparison
> > Sorting.
>
> Thanks, I will do that if I can find it.
> (I got volume one at a garage sale, and
> I've never seen any of the others anywhere.)

Knuth is an excellent example of a bit twiddler in action. As far as I'm
concerned the point gets lost in a sea of details written in mix.


greetings,

Re: Smart sorting algorithm ?

[Florian Weimer]

achrist@easystreet.com writes:

> 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.   

Quicksort performs quite a lot of comparisons (for an O(n log n)
algorithm, of course).  It gains its speed from the tightness of its
inner loop, not from saving comparisons.

Re: Smart sorting algorithm ?

[achrist]

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

Re: Smart sorting algorithm ?

[Wes Groleau]

> 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 matter of fact, this particular implementation
_several_ times compared an item with itself!

-- 
Wes Groleau
http://freepages.rootsweb.com/~wgroleau

Re: Smart sorting algorithm ?

[achrist]

Wes Groleau wrote:
> 
> > 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 matter of fact, this particular implementation
> _several_ times compared an item with itself!
> 

I think that's an optimization of the tight inner loop that is based on
the assumption that one extra item compare is less expensive than
comparing indexes on every iteration of the loop plus keeping track of
where your pivot element is.  That comparison of an element with itself
will end the inner loop.  In your case, the assumption is maybe not
true, but you get at most one extra compare on the last time through the 
loop.  I think you can change the loop to save the comparison, but it 
makes the algorithm more complicated and it's easy to get it wrong.  I 
believe I've done that.

Al

Re: Smart sorting algorithm ?

[Wes Groleau]

> I think that's an optimization of the tight inner loop that is based on
> the assumption that one extra item compare is less expensive than
> comparing indexes on every iteration of the loop plus keeping track of
> where your pivot element is.  That comparison of an element with itself
> will end the inner loop.  In your case, the assumption is maybe not
> true, but you get at most one extra compare on the last time through the
> loop.  I think you can change the loop to save the comparison, but it
> makes the algorithm more complicated and it's easy to get it wrong.  I
> believe I've done that.

Actually, once someone gave me the clue-by-four
of "insertion with binary search" I re-wrote it
that way in less than two hours, under 50 SLOC
(including assertions).  Far simpler than the
quicksort I borrowed, and no compare (X,X).

-- 
Wes Groleau
http://freepages.rootsweb.com/~wgroleau

Re: Smart sorting algorithm ?

[Robert Dewar]

"Tarjei T. Jensen" <tarjei.jensen@kvaerner.com> wrote in message news:<aft22d$bcm2@news.kvaerner.com>...
> Wes Groleau wrote:
> > > have a look into D.E.Knuth: The Art of Computer Programming, Vol
> > > 3: Sorting and Searching. Subsection 5.3.1: Minimum Comparison
> > > Sorting.
> >
> > Thanks, I will do that if I can find it.
> > (I got volume one at a garage sale, and
> > I've never seen any of the others anywhere.)
> 
> Knuth is an excellent example of a bit twiddler in action. As far as I'm
> concerned the point gets lost in a sea of details written in mix.

Not at all. I suspect you have not really made an effort to read these
books carefully. The point of the MIX sections (which are a very small
fraction of the material) is to try to analyze *actual* performance of
algorithms as opposed to theoretical O(f(n)) behavior. It's an interesting
attempt, not made by any other algorithm book author, and indeed not always
successful since it involves going to a very low level, but it is not clear
that there is any way of doing this that would be more successful.

In fact all algorithms in Knuth are stated in a very readable pseudo-language
and if you do not care for the detailed performance analysis in the MIX
code sections, just skip them, but don't throw out the baby with the bath
water, and don't use the MIX sections as an excuse not to thoroughly read
the material in the first three Knuth volumes (and if you have the math,
follow through the mathematical reasoning carefully).

Re: Smart sorting algorithm ?

[Ron]

First, I hope Wes has investigated non-comparison-based sorting...

Second, Wes never indicated the number of items to sort, but used small
values (18 and 36) as examples.  If you only want to sort a small number of
items, then the On-Line Encyclopedia of Integer Sequences
(http://www.research.att.com/~njas/sequences/index.html) may be of help:
To sort 18 items (referenced by sequence number):
A036604 lists the minimal number of comparisons needed to sort n elements,
but only goes up to n=12.
A003070 gives 53 for ceiling(log_2 n!) (the lower bound on number of
comparisons required for comparison-based sorting)
A001768 gives 54 comparisons for merge sort
A001855 gives 59 comparisons for sorting by binary insertion
A003071 gives 67 comparisons for sorting by list merging
A006282 gives 82 comparisons for Batcher's parallel sort (which can be
implemented via a sorting network)
Also, the best sorting network I'm aware of requires 79
comparison-exchanges.

Third, quicksort isn't very good for a small number of items because of its
worst-case performance and overhead, which is why most sorting algorithms
based upon quicksort us another sorting method once the sub-lists are small.

Good luck!


- Ron Zeno

Re: Smart sorting algorithm ?

[Wes Groleau]

> Anyone know anything about a sorting algorithm
> that includes the ability to infer the answer
> to a comparison from comparisons already done?

I solved this part.  Wrote an "<" that
first checks a 2D lookup table.  If the 
answer is "unknown" it does the comparison,
then updates as many cells in the table as
possible.  Once you compare A & B, you may
be able to determine (and record) the
order of A,C based on B,C or vice versa.

> The reason I'm asking is that I have a situation
> where deciding the order of two items is very slow.

Since the actual comparison was the bottleneck,
the choice of sorting algorithms doesn't matter
any more.

-- 
Wes Groleau
http://freepages.rootsweb.com/~wgroleau

Re: Smart sorting algorithm ?

[Robert Dewar]

Wes Groleau <wesgroleau@despammed.com> wrote in message news:<3D2A0A25.52A62B7C@despammed.com>...
> > Anyone know anything about a sorting algorithm
> > that includes the ability to infer the answer
> > to a comparison from comparisons already done?
> 
> I solved this part.  Wrote an "<" that
> first checks a 2D lookup table.  If the 
> answer is "unknown" it does the comparison,
> then updates as many cells in the table as
> possible.  Once you compare A & B, you may
> be able to determine (and record) the
> order of A,C based on B,C or vice versa.

That's just got to be a non-optimal solution. You just
can't get below NlogN comparisons this way, so why not
just use a decent NlogN comparison algorithm in the first
place (e.g. GNAT.Heap_Sort_A). I think you are wasting
your time here.

Re: Smart sorting algorithm ?

[tmoran]

> I solved this part.  Wrote an "<" that
> first checks a 2D lookup table.  If the
> answer is "unknown" it does the comparison,
> then updates as many cells in the table as
> possible.  Once you compare A & B, you may
  Though it's a rather different data structure, it sounds like it will
probably do the same comparisons as building a binary tree, which is
not good if your data might arrive already in order.

Re: Smart sorting algorithm ?

[Ron]

"Wes Groleau":
> Wrote an "<" that
> first checks a 2D lookup table.  If the
> answer is "unknown" it does the comparison,
> then updates as many cells in the table as
> possible.

Smart.  You avoid making the same comparison more than once and learn from
transitivity...  No matter what sorting algorithm you use, the table keeps
the number of comparison down to nC2=n(n-1)/2 comparisons.  The gain from
transitivity will depend upon your sorting algorithm, but some will give you
no gain at all...

> Since the actual comparison was the bottleneck,
> the choice of sorting algorithms doesn't matter
> any more.

No.  Though you never gave the range of the number of items to sort, even
for small lists the difference between the worst case (nC2 = n(n-1)/2
comparisons) and an O(nlog(n)) sorting algorithm such as heapsort
(~ceiling(ln(n!)/ln(2) for small n) is very large.  That's 86 more
comparisons for n=18 and 489 more for n=36.  You want to minimize the number
of comparisons, so you need to select a good sorting algorithm...


- Ron Zeno

Re: Smart sorting algorithm ?

[Ron]

"Wes Groleau" :
> Wrote an "<" that
> first checks a 2D lookup table.

I mentioned earlier that you should investigate non-comparison-based
sorting.  If you can easily create a lookup table, then you should easily be
able to create such a sorting algorithm.  O(n) and O(1) comparison sorting
is possible under special circumstances...


- Ron Zeno

Re: Smart sorting algorithm ?

[Wes Groleau]

> Smart.  You avoid making the same comparison more than once and learn from
> transitivity...  No matter what sorting algorithm you use, the table keeps
> the number of comparison down to nC2=n(n-1)/2 comparisons.  The gain from
> transitivity will depend upon your sorting algorithm, but some will give you
> no gain at all...

Someone suggested by e-mail/CGI (no return address)
that I use bucket sort.  But that won't work: the
items have an order, but no numeric value until
the sorting is complete.  Hence there is no way
to assign any particular item to any particular
bucket until the sorting is complete.

Background: We're taking a set of strings and
asking a human to make a better/worse value
judgment on each pair.

The only numeric value is the position in
the sorted list.  The lookup table for
transitivity uses the position in the unsorted
list.  

   "<" (L,R) is: if L better than R, return true

   ....

   Lookup : .... := (others => (others => Unknown));

   ....

   if Input (A) < Input (B) then

      Lookup (A,B) := Correct;

      if Lookup (B,C) = Correct then

         -- inference
         Lookup (A,C) := Correct;

If "=" is prevented or disallowed, then there are
four inferences for every C, and C loops through
Input'Range.  Recursion could add more inferences
for each inference made.

-- 
Wes Groleau
http://freepages.rootsweb.com/~wgroleau

Re: Smart sorting algorithm ?

[tmoran]

>asking a human to make a better/worse value judgment on each pair.
Do you have grounds to believe the human's preferences are transitive?

Re: Smart sorting algorithm ?

[Wes Groleau]

tmoran@acm.org wrote:
> >asking a human to make a better/worse value judgment on each pair.
> Do you have grounds to believe the human's preferences are transitive?

No, but I have three defenses against that:

1. Get a second opinion and merge.

2. Don't ask, don't tell.  If they picked A over B and
   B over C don't even mention A vs. C (which was the
   whole point all along).  The point of the whole thing
   is ranking/prioritizing/whatever-you-call-it.

3. If they actually notice and complain that C comes
   before A, say, "Sorry, time (or 'the list') is
   linear.  Only one can be first."

Also, that's not necessarily the only application.
But it is my current application.

-- 
Wes Groleau
http://freepages.rootsweb.com/~wgroleau

Re: Smart sorting algorithm ?

[Wes Groleau]

> I mentioned earlier that you should investigate non-comparison-based
> sorting.  If you can easily create a lookup table, then you should easily be
> able to create such a sorting algorithm.  O(n) and O(1) comparison sorting
> is possible under special circumstances...

The lookup table is created by doing the comparisons.
And predicting some comparisons from others.
Once that's done, the row with the N "this is first"
entries is first.  Second is the row with N-1, etc.
But the whole process still involves some comparisons.

-- 
Wes Groleau
http://freepages.rootsweb.com/~wgroleau

Re: Smart sorting algorithm ?

[Robert Dewar]

Wes Groleau <wesgroleau@despammed.com> wrote in message news:<3D2D98DB.39944A80@despammed.com>...
> 
> The lookup table is created by doing the comparisons.
> And predicting some comparisons from others.
> Once that's done, the row with the N "this is first"
> entries is first.  Second is the row with N-1, etc.
> But the whole process still involves some comparisons.

Once again, this is a dead-end idea. It cannot possibly
be any help if you are using a good sorting algorithm
that minimizes comparisons in the first place, and if
minimizing comparisons is desirable, then that should
be the starting point, and you should forget about this
kludging around trying to repair bad sorting algorithms.

Re: Smart sorting algorithm ?

[Wes Groleau]

> Once again, this is a dead-end idea. It cannot possibly

Well, I'm not convinced--although I do respect
your higher-than-mine education and experience
in this area.  If you provide a "proof" or
a link to a proof, I'll try to understand it.
Intuitively, I get foggy images of why it might
be true, but the wishful thinking is quite
powerful in this case.

> be any help if you are using a good sorting algorithm
> that minimizes comparisons in the first place, and if

I am convinced of the value of such,
but since that is not enough in this case......

-- 
Wes Groleau
http://freepages.rootsweb.com/~wgroleau

Re: Smart sorting algorithm ?

[achrist]

If you have to invent something to improve the process, where
comparisons are done by humans according to rules unknown, then
there is perhaps some chance to improve the overall speed.  Can 
you give the humans lists of 5-20 items at a time to sort, and
use the information from these sorted sub-lists in some near 
optimal way to produce an overall sort order?   If there is any
machine algorithm that can get you into the neighborhood and put an
approximately sorted list of a few items on  a screen for the person 
to re-arrange into a correctly sorted list,  you should be able to
extract information from the human much faster than you would be
getting it by presenting simple pairwise comparisons.  

The optimal algorithm when comparisons are m-way like that IDK, but 
coming up with one should give lots of opportunity for you to be
creative.


Al 

Wes Groleau wrote:
> 
> > Once again, this is a dead-end idea. It cannot possibly
> 
> Well, I'm not convinced--although I do respect
> your higher-than-mine education and experience
> in this area.  If you provide a "proof" or
> a link to a proof, I'll try to understand it.
> Intuitively, I get foggy images of why it might
> be true, but the wishful thinking is quite
> powerful in this case.
> 
> > be any help if you are using a good sorting algorithm
> > that minimizes comparisons in the first place, and if
> 
> I am convinced of the value of such,
> but since that is not enough in this case......
> 
> --
> Wes Groleau
> http://freepages.rootsweb.com/~wgroleau