[racket] Looking for feedback on code style

On 9/13/10 1:34 PM, Phil Bewig wrote:
> Fixed.  See the comment at
> http://programmingpraxis.com/2009/12/11/selection/.
>
> Prabhakar:  You are correct that shuffling once at the beginning is
> sufficient.  But I am interested in your critique of shuffling.  Do you
> know a better way to shuffle a list than to convert it to a vector,
> shuffle in place, then convert back to a list?  You might look at this
> discussion:
> http://groups.google.com/group/comp.lang.scheme/browse_thread/thread/24270db01f684439/e54c99564028efec.
>   The list-vector-list method is O(n); any functional method appears to
> be O(n log n).

I don't know of a purely-functional way to shuffle a list of length n 
(where every permutation is equally likely) in o(n log n) time 
("little-o"). It's an interesting problem.

But the reason that the randomized selection algorithm takes O(n) time 
with high probability is that it discards chunks of the original list, 
avoiding the overhead of going over them again and again. The depth of 
the recursion is still Omega(log n) with high probability, but the size 
of the recursion is getting small fast enough that that doesn't matter.

By choosing a random pivot each time, instead of a deterministic pivot 
after an expensive shuffling operation, you reap the same benefit, you 
get the O(n) running time (w.h.p), the code is clearer, and the analysis 
is easier (because each pivot choice is independent of earlier ones). --PR