[racket] Partion

From: Danny Yoo (dyoo at cs.wpi.edu)
Date: Sun Mar 18 19:38:50 EDT 2012

> Followup: "quickselect" is the name of this:

Hi Jens,

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


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>

Posted on the users mailing list.