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