[racket] Partion

On Fri, Mar 16, 2012 at 3:26 PM, Jens Axel Søgaard
<jensaxel at soegaard.net> wrote:
> 2012/3/16 Danny Yoo <dyoo at cs.wpi.edu>:
>
>> Hmmm... the behavior of quicksort almost feels like what you want; in
>> the optimal case, it's supposed to choose the median, and then
>> partition elements into things bigger or less than the median.  You
>> might be able to get away with an in-place quicksort that's stops
>> early.  Your problem doesn't require a total sort, but rather just
>> enough order that we can say that all the elements on the left half
>> are smaller than all the elements on the right.
>
> I just realized that I don't need to use the builtin partition to
> split the list. I can just run through the list and collect elements
> less or equal to the median until I have collected (half N) elements.
>
> Apropos, should median and select (kth-element)  be in racket/list ?

FWIW, there are well-known parallel algorithms for these.

Robby