[racket] Partion

On Fri, Mar 16, 2012 at 4:11 PM, Jens Axel Søgaard
<jensaxel at soegaard.net> wrote:
> 2012/3/16 Danny Yoo <dyoo at cs.wpi.edu>:
>
>> Hmmm... Questions: why is a list-based approach a requirement?
>
> Er. Well. A vector based solution would be fine too.
>
>> Do the
>> numbers share a special characteristic, such as being densely packed
>> into a tight range?  If so, bucket sorting could be applied to get
>> fast O(n) sorting at this stage.
>
> The numbers are coordinates of the corners of bounding rectangles
> of two-dimensional objects. I don't expect a particular distribution.


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.