<div><div>Hello,<br><br>ok, but this still means, that you have to rewrite the algorithm to get<br>an efficient qsearch for arbitrary k. Are there any popular algorithms <br>whose overall complexity is improved by lazyness? Or where you
<br>get such special cases as free lunch? Such an algorithm could be <br>useful as a motivating example of Haskell for the talk at the open <br>source conference (that is currently discussed at haskell-cafe).<br>These people are mostly really excited about performance :-)
<br><br>Best regards,<br><br>Steffen<br><br> </div><br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">Apparently, I did not think enough about quicksort :) as it is well
<br>capable of delivering the minimum element in O(n) time. In fact, given<br>proper pivot choice,<br><br> take k . qsort<br><br>is the optimal O(n + k log k) algorithm for returning the first k<br>smallest elements in sorted order! See also
<br><br> <a href="http://en.wikipedia.org/wiki/Selection_algorithm">http://en.wikipedia.org/wiki/Selection_algorithm</a><br><br><br>Let's assume that the quicksort in<br><br> qsort [] = []<br> qsort (x:xs) = qsort ls ++ [x] ++ qsort rs
<br> where<br> ls = filter (< x) xs<br> rs = filter (>= x) xs<br><br>always uses a good pivot x, i.e. that ls and rs have around n/2 elements<br>each. As long as this n/2 is greater than k, taking the first k elements
<br>does not evaluate the second recursive call to quicksort. In other<br>words, it takes<br><br> O(n) -- for filtering xs during the initial call to qsort<br> + O(n/2) -- same as above but with the first half of the list
<br> + O(n/4) -- filtering the half of the half<br> + ...<br> + O(k)<br> ________<br> < O(n + n/2 + n/4 + n/8 + ...) = O(n)<br><br>time until ls has fewer than k elements. When this becomes the case, the<br>argument list to the recursive call to qsort has a size of at most 2*k
<br>and it takes at most O(k log k) time finish sorting it completely and<br>taking the first k elements of this. This gives a total of O(n + k log k).<br><br>Regards,<br>apfelmus<br><br>_______________________________________________
<br>Haskell mailing list<br><a href="mailto:Haskell@haskell.org">Haskell@haskell.org</a><br><a href="http://www.haskell.org/mailman/listinfo/haskell">http://www.haskell.org/mailman/listinfo/haskell</a><br></blockquote></div>
<br><br clear="all"><br>-- <br>Dipl.-Inform. Steffen Mazanek<br>Institut für Softwaretechnologie<br>Fakultät Informatik<br><br>Universität der Bundeswehr München<br>85577 Neubiberg<br><br>Tel: +49 (0)89 6004-2505<br>Fax: +49 (0)89 6004-4447
<br><br>E-Mail: <a href="mailto:steffen.mazanek@unibw.de">steffen.mazanek@unibw.de</a>