[Haskell-cafe] k-minima in Haskell

[ajb at spamcop.net]

G'day all.

Quoting raghu vardhan <mrvr84 at yahoo.co.in>:

> So, any algorithm that sorts is no good (think of n as huge, and k small).

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.

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.

Cheers,
Andrew Bromage