On Thu, 16 Dec 2004 02:05:42 +0900
Neil Spring <nspring / cs.washington.edu> wrote:

> On Dec 14, 2004, at 7:24 PM, Ilmari Heikkinen wrote:
> > rand.rb is a library for picking random elements and shuffling.
> > This work is licensed under the same terms as Ruby itself.
> 
> umm,  could you maybe replace:
> 
>    def shuffle!
>      sort!{rand <=> 0.5}
>    end
> 
> with:
> 
>    def shuffle!
>      each_index {|j| i = rand(size-j); self[j], self[j+i] = self[j+i], 
> self[j]}
>      self
>    end
> 
> I would not rely on sort to do the right thing, and it is less 
> efficient than necessary.  I use the second shuffle code extensively in 
> my code which deals with shuffling lots and lots of elements.  
> Presumably the second is O(n) where the sort based scheme is at best 
> O(n log n).  A little googling suggests this is the "Fisher-Yates 
> shuffle."
> 

I don't know if the first proposed solution is valid, because it depends on how
sort is implemented and if the sort algorithm makes each comparision only once.
Otherwise I imagine weird things happening, if elements change their order
while sorting.

So the correct way to do this is

    sort_by{rand}

Fisher Yates is a nice, unbiased O(n) shuffler. I personally more often use the
sort shuffler, because it is so amazingly wordy and I can remember it.

Regards,

Brian

-- 
Brian Schröäer
http://www.brian-schroeder.de/