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

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

From:
Glenn Linderman
Date:
July 5, 2004 18:38
Subject:
Re: optimizing Short circuiting sort method based on [M]
Message ID:
40EA0285.2050807@nevcal.com
On approximately 7/5/2004 5:33 PM, came the following characters from
the keyboard of david nicol:

> I am wondering if I was somehow unclear in my proposed algorithm,
> archived at 
> 
> http://www.xray.mpe.mpg.de/mailing-lists/perl5-porters/2004-06/msg00592.html
> 
> which describes both bubble and inserting to place new elements in the
> short list.  

The algorithm seemed clear enough to me, but I couldn't figure out why 
you were interested in dealing with the short list.... if the bubble or 
heap sort on the long list returns data in sorted order, which it 
should, then

   push @short_list, &next_elem_from_incremental_sort();

should be adequate and optimal for putting data into the short list. 
This is sufficiently trivial that additional or alternative algorithms 
are not particularly interesting to me.

The interesting part of the job is figuring out how to pull the sorted 
data out of the long list without doing a complete sort, and without 
paying inordinate overhead needed by some fast sort algorithms, which 
are definitely worthwhile when sorting the whole list, but are not 
nearly as worthwhile when only needing a few elements.

-- 
Glenn -- http://nevcal.com/
===========================
The best part about procrastination is that you are never bored,
because you have all kinds of things that you should be doing.




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