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 box?
No, as far as I thought about quicksort, it needs O(n log n) to produce the first element. But even the mergesort implementation has to be chosen carefully as I've seen many that still need O(n log n) just to return the smallest element.
Apparently, I did not think enough about quicksort :) as it is well capable of delivering the minimum element in O(n) time. In fact, given proper pivot choice, take k . qsort is the optimal O(n + k log k) algorithm for returning the first k smallest elements in sorted order! See also http://en.wikipedia.org/wiki/Selection_algorithm Let's assume that the quicksort in qsort [] = [] qsort (x:xs) = qsort ls ++ [x] ++ qsort rs where ls = filter (< x) xs rs = filter (>= x) xs always uses a good pivot x, i.e. that ls and rs have around n/2 elements each. As long as this n/2 is greater than k, taking the first k elements does not evaluate the second recursive call to quicksort. In other words, it takes O(n) -- for filtering xs during the initial call to qsort + O(n/2) -- same as above but with the first half of the list + O(n/4) -- filtering the half of the half + ... + O(k) ________ < O(n + n/2 + n/4 + n/8 + ...) = O(n) time until ls has fewer than k elements. When this becomes the case, the argument list to the recursive call to qsort has a size of at most 2*k and it takes at most O(k log k) time finish sorting it completely and taking the first k elements of this. This gives a total of O(n + k log k). Regards, apfelmus