[racket] Partion

From: Danny Yoo (dyoo at cs.wpi.edu)
Date: Fri Mar 16 16:43:24 EDT 2012

> 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.

Followup: "quickselect" is the name of this:


Posted on the users mailing list.