Shuffle() - change of algorithm needed (also relevant for array_rand())

Resent due to lack of feedback. Objections against me changing it to the behaviour I described below? --Jeroen ----- Original Message ----- From: "Jeroen van Wolffelaar" <jeroen@a-eskwadraat.nl> To: "PHP Developers Mailing List" <php-dev@lists.php.net> Sent: Monday, October 15, 2001 9:45 PM Subject: 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. > > Note 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 > >