Steffen Mazanek wrote:
ok, but this still means, that you have to rewrite the algorithm to get
an efficient qsearch for arbitrary k.
You mean the case when you only want the k-th minimum but not the
others? Well, you can make this work with qsort, too.
The fundamental solution would be to
Hello,
ok, but this still means, that you have to rewrite the algorithm to get
an efficient qsearch for arbitrary k. Are there any popular algorithms
whose overall complexity is improved by lazyness? Or where you
get such special cases as free lunch? Such an algorithm could be
useful as a
apfelmus wrote:
Steffen Mazanek wrote:
From my understanding for small k's lazy
evaluation already does the trick for the naive quicksort
algorithm (quicksort smaller ++ [x] ++ quicksort greater),
doesn't it? Is there a search algorithm that makes better
use of lazy evaluation out of the
Steffen Mazanek wrote:
say, we want to find the k'th element in a sorted list.
I assume that you want to find the k'th smallest element of an unsorted
list by sorting it?
[...]
However, I was wondering whether it might be possible
to implement quicksort in a way that quicksearch is
done