# [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
*