Re: Bug #7045 Updated: Shuffle() does behave correctly

> ID: 7045 > Updated by: derick > Reported By: fp@cedemo.com > Old Status: Analyzed > Status: Open > Bug Type: Arrays related > Operating System: Linux RH 6 and 7 > PHP Version: 4.0.1pl2 > New Comment: <snip> > [2000-10-30 10:07:36] stas@php.net > > This is probably the property of sort algorithm used in shuffle. Whoever wrote it, please take attention! The algorithm is a mergesort with a random comparer. That's not going to give a well shuffle. There are a few alternatives. First, it's important to know wether one can random-access the array. IIRC, that's not possible. So the straight forward O(n) algorithm won't work directly (well, it'll work, but definitely not in O(n)). It can be easily made to work by simply indexing the array first (from outside). It's straight forward, and thus quite easy to assure that it's correct, and quite easy to implement too. The external indexing step is also O(n), so speed isn't dramatically affected. Not that this algortihm is a lot faster than the current one. Mergesort is O(nlogn), with more memory usage, and quite heavier draw on the random number generator. NB: also the array_rand() function has a bad algorithm. The same algorithm could and should be used, it also elimintates the use of shuffle inside array_rand(). --Jeroen