On Sat, Mar 12, 2016 at 12:06 PM, William D Clinger <xxxxxx@ccs.neu.edu> wrote:
> In a previous message, I wrote:
>
>> The specification of vector-select! is missing an ordering predicate.
>> It is also said to run "in O(k) time", which is impossible because it
>> must examine start-end elements, which is arbitrarily larger than k.
>
> Now that I have implemented that procedure, I think it's a really
> strange procedure for this SRFI to be specifying.

Another way of naming it is top-k.  Finding the smallest (or largest)
k elements of a collection is so useful I find I rarely write a program
these days that doesn't use it.  Most of the time, but not always,
I find I want to further sort those elements (i.e. a partial sort).

The implementation you provide is O(n log n), whereas the
implementation I posted to the list in January is O(n).  Partial sorting
would be O(n + k log k).

--
Alex