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
_________________________________________________
For list-related administrative tasks:
http://lists.racket-lang.org/listinfo/users
