On (03 May 2001 10:23:15 +0300) you wrote:
> Michael Schwern:
> >
> > Would be neat if: my($first) = grep {...} @list; knew to stop itself, yes.
> >
> > It also reminds me of mjd's mention of: my($first) = sort {...} @list;
> > being O(n) if Perl were really Lazy.
>
> But it would need a completely different algorithm.
Not precisely. If you have lazy evaluation, then quicksort is exactly
what is wanted here. For example, if you implement qsort in the
straightforward way in Haskell, and write
min = first quicksort list;
then it *does* run in O(n) time; in this case qucksort reduces to
Hoare's algorithm for min.
> my ($first, $second, $third) = sort {...} @list;
The Haskell version of this also runs in O(n) time.
> is kind-of plausible. So we'd definitely want
>
> ((undef)x((@list+1)/2), $median) = sort {...} @list;
The Haskell equivalent of this (still using quicksort) runs in O(n log
n) time, which I believe is optimal for finding the median.
