[racket] Partion

> Followup: "quickselect" is the name of this:
>
>
http://en.wikipedia.org/wiki/Selection_algorithm#Partition-based_general_selection_algorithm

Hi Jens,

I've coded this algorithm up with a few minimal test cases:

   https://github.com/dyoo/quick-select

It should do the trick, though you'll need to modify it to abstract
"lest-than?" so it's not hard-coded to numbers.  So you should, with some
adjustments, do something like:

   (define a-vec ...) ;; collection of your elements
   (quick-select! a-vec
                         0 (sub1 (vector-length a-vec))
                         (quotient (vector-length a-vec) 2))

purely for quick-select!'s side effect on a-vec: all the elements in the
first half should be less than or equal to the elements on the right half.

(The really annoying part about the description on Wikipedia is that it's
useless without expressing the domains of the arguments..)


Best of wishes!
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20120318/b6056b26/attachment.html>