> Followup: "quickselect" is the name of this:<br>><br>> <a href="http://en.wikipedia.org/wiki/Selection_algorithm#Partition-based_general_selection_algorithm">http://en.wikipedia.org/wiki/Selection_algorithm#Partition-based_general_selection_algorithm</a><br>
<br>Hi Jens,<br><br>I've coded this algorithm up with a few minimal test cases:<br><br> <a href="https://github.com/dyoo/quick-select">https://github.com/dyoo/quick-select</a><br><br>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:<br>
<br> (define a-vec ...) ;; collection of your elements<br> (quick-select! a-vec <br> 0 (sub1 (vector-length a-vec))<br> (quotient (vector-length a-vec) 2))<br><br>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.<br>
<br>(The really annoying part about the description on Wikipedia is that it's useless without expressing the domains of the arguments..)<br><br><br>Best of wishes!