[racket] Partion

Do you mean a quicksort that performs only the filtering functionality around a pivot? QS is 'cheap' because the assumption is that you can pick a good pivot. What if you also pass along weights that tell you how many of the numbers you want in each part? It's 1/2 and 1/2 initially but as you fail to get it right you can focus on the part that is too large and get enough numbers back from there. -- Matthias








On Mar 16, 2012, at 4:18 PM, Danny Yoo wrote:

> 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.
> 
> ____________________
>  Racket Users list:
>  http://lists.racket-lang.org/users