From: Dan Zwell <dzwell@...>
Date: 2007-04-30T16:41:08+09:00
Subject: Re: sorting by rand?

Peter Seebach wrote:
>> If the numbers that rand() generates are good enough, the chance of 
>> collisions preserving order should be the same as the chance of the next 
>> iteration of randomizing putting them back in the same order, shouldn't it?
> 
> I think not quite.  Imagine a hypothetical pair of entities.  They have a
> 1/bignum chance of a collision, which preserves their relative sorting.
> 
> If you do it twice, the probability that the same pair of entities collided
> both times is 1/bignum^2.  They might otherwise end up in the same order, or
> not, but there's only a 1/bignum^2 chance that they ended up in the same
> order *due to a collision*.
> 
> -s
> 
> 

You're right. I guess I'm just inclined to discount a such a small 
difference in orderings. And the difference in our benchmarks may have 
been due to the fact that I'm using a different algorithm (for each 
element i, swap i with an element from i...end). Or perhaps because I 
have more method calls, as I made a method Array#randomize! (that calls 
Array#swap! n times)

Dan