note 37397 added to function.shuffle

Here's an implementation of a canonical shuffling algorithm. Its O(n), not O(n^2). The implementation of Fisher-Yates below uses array splicing inside a for loop over the array, making it O(n^2). It creates a uniform distribution of permutations - the definition of a shuffle. I'm not sure that all of the ad hoc algorithms below do this - they might create shuffles that look random on casual inspection, but aren't. Many implementations of Fisher-Yates check to make sure that $i != $j before swapping. I figure that for large lists, that check incurs more cost than just swapping every time. /** * Shuffles an array using the Fisher-Yates shuffle. * * D. E. Knuth: The Art of Computer Programming, Volume 2, * Third edition. Section 3.4.2, Algorithm P, pp 145. Reading: * Addison-Wesley, 1997. ISBN: 0-201-89684-2. * * R. A. Fisher and F. Yates: Statistical Tables. London, 1938. * Example 12. * * @author Justin Knoll * @param array The array to be sorted - passed by reference. * @return The shuffled array. */ function fisherYatesShuffle(&$array) { for ($i = count($array); --$i; $i > 0) { $j = @mt_rand(0, $i+1); $temp = $array[$i]; $array[$i] = $array[$j]; $array[$j] = $temp; } } ---- Manual Page -- http://www.php.net/manual/en/function.shuffle.php Edit -- http://master.php.net/manage/user-notes.php?action=edit+37397 Delete -- http://master.php.net/manage/user-notes.php?action=delete+37397&report=yes Reject -- http://master.php.net/manage/user-notes.php?action=reject+37397&report=yes Search -- http://master.php.net/manage/user-notes.php