On Sun, Mar 10, 2002 at 10:16:05PM +0000, Jonathan E. Paton wrote:
> > > 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?
No. My second first was a statement of time. Lazy evaluation means that
you don't calculate what you need to calculate. But that doesn't mean
that any sort algorithm can find the smallest element in linear time,
just by making it lazy. A typical heap sort implementation finds the
elements from large to small, taking O (log n) for each next element,
after an initial O (n) preprocessing time. And you get to the smallest
element only after finding all the other elements.
> 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.
No, it's not. It's O (n log X).
Abigail
