Front page | perl.fwp |
Postings from March 2002
> > PS With a truly lazy sort you'd be able to do...
> >
> > ($first) = sort { $a wibble $b } @big_list; # in O(n)
> time.
>
> Not necessarely - it would depend on the underlaying
> sorting mechanism.
It wouldn't be lazy then, would it?
> Shell sort and heap sort for instance don't get the
> first element first.
Huh? Are you saything that those sorting algorithms
don't actually sort?
I think the idea of "Lazy sort" is in certain
circumstances, say for first X highest items, then you
can switch to a different and faster algorithm.
A lazy sort can be done in n time, easily:
@highest;
foreach element {
if (element > lowest in @highest) {
stick in @highest, removing lowest in @highest;
}
}
return sort @highest
The Big Oh of that is n.
Jonathan Paton
__________________________________________________
Do You Yahoo!?
Everything you'll ever need on one web page
from News and Sport to Email and Music Charts
http://uk.my.yahoo.com
Thread Previous
|
Thread Next