develooper Front page | perl.perl5.porters | Postings from July 2004

Re: optimizing Short circuiting sort method based on [M]

From:
John P. Linderman
Date:
July 7, 2004 07:39
Subject:
Re: optimizing Short circuiting sort method based on [M]
Message ID:
200407071439.KAA27006@raptor.research.att.com
david nicol asked for comments thus:
> On Tue, 2004-06-29 at 18:24, Glenn Linderman wrote:
> 
> > I'm not sure offhand how many result elements are at the crossover 
> > between where bubble sort is best and heapsort becomes best, but I 
> > believe both of  those will generate entries in sorted order faster than 
> > sorting the whole array to throw away most of the results.
> 
> That is what I was trying to figure out, and I would like peer review
> on my result of bubble for five or less and heap for six or more.  M=5
> is the judgement call, giving always two (after the unavoidable initial
> comparison) in insertion mode whereas bubble gives an expected two with
> random data.

I meant to reply to the porters at large earlier, but succeeded in only
contacting a couple people.  Heap sort is going to double the number
of comparisons realtive to a binary search, since it has to do two
compares at each level of the log M tree.  It saves moves, but moves
are cheap, and comparisons are dear, so I don't see heap sort ever
being the winner.  You can get N log M comparisons from the binary
search you have at
http://www.xray.mpe.mpg.de/mailing-lists/perl5-porters/2004-06/msg00592.html
and N * M moves, which will beat the wholesale sorts for small enough M.
But the wholesale merge sort does a nice job on orderly data, and will
beat the specialized sort if there are fewer than log M runs, for example.
I can imagine keeping track of where insertions happen, and biasing the
initial guess-point for the binary search when it appears the data are
non-random.  That could make comparisons look more like N than like N log M
for orderly data.  -- jpl



nntp.perl.org: Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at ask@perl.org | Group listing | About