[racket] Partion

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 ?

--
Jens Axel Søgaard