raghu vardhan
So, any algorithm that sorts is no good (think of n as huge, and k small).
With lazy evaluation, it is! http://article.gmane.org/gmane.comp.lang.haskell.general/15010 ajb@spamcop.net wrote:
The essence of all the answers that you've received is that it doesn't matter if k is small, sorting is still the most elegant answer in Haskell.
(It's not only most elegant, it can even be put to work.)
The reason is that in Haskell, a function which sort function will produce the sorted list lazily. If you don't demand the while list, you don't perform the whole sort.
Some algorithms are better than others for minimising the amount of work if not all of the list is demanded, but ideally, producing the first k elements will take O(n log k + k) time.
You mean O(k * log n + n) of course. Regards, apfelmus