Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:15:23
David R. Conrad (drc@adni.net)
Thu, 29 Oct 1998 21:07:09 -0500 (EST)
On Thu, 29 Oct 1998, Anonymous wrote:
> A couple responders have said there is no SWAP_TIMES
> which would work. But I don't understand why the
> following wouldn't work:
>
> [M]ake sure that x and y can't be equal, since
> there's no point in swapping an element with itself.
>
> Now, simply calculate how many SWAP_TIMES it would take for it
> to be equally as likely that an element would not be touched as
> it would to land in its original spot.
>
> (255/256)^(t*2) = 1/256
> or
> t = ln(1/256)/(2*ln(255/256))
> or
> 708.3955
Even assuming that you can safely trust this number (I wouldn't), why
would you bother with an algorithm that required more than 256 iterations
when there is one which only requires 256?
Someone else already posted the well-known O(n) algorithm to which I'm
referring, so I won't repeat it here, but I would commend it to you.
David R. Conrad <drc@adni.net>
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:15:23