<p>I was asked this question in a job interview. The interviewer and I disagreed on what the correct answer was. I'm wondering if anyone has any data on this.</p>

<p>Update: I should have mentioned that the use of shuffle() was strictly forbidden... sorry.</p>

[{'answer_id': 65978, 'author': 'Loren Segal', 'author_id': 6436, 'author_profile': 'https://Stackoverflow.com/users/6436', 'pm_score': 2, 'selected': False, 'text': '<pre><code>shuffle($arr);\n</code></pre>\n\n<p>:)</p>\n\n<p>edit: I should clarify... my definition of best involves not just algorithm efficiency but code readability and maintainability as well. Using standard library functions means maintaining less code and reading much less too. Beyond that, you can get into year-long debates with PhD professors about the best "true random" function, so somebody will always disagree with you on randomization questions.</p>\n'}, {'answer_id': 66039, 'author': 'Community', 'author_id': -1, 'author_profile': 'https://Stackoverflow.com/users/-1', 'pm_score': 0, 'selected': False, 'text': '<p>The "correct" way is pretty vague. The best (fastest / easiest / most elegant) to sort an array would be to just use the built-in shuffle() function.</p>\n'}, {'answer_id': 66433, 'author': 'bryanpearson', 'author_id': 9803, 'author_profile': 'https://Stackoverflow.com/users/9803', 'pm_score': 0, 'selected': False, 'text': '<p>PHP has a built in function --> shuffle() . I would say that should do what you like, but it mostly likely will be anything but totally \'random\'. </p>\n\n<p>Check <a href="http://computer.howstuffworks.com/question697.htm" rel="nofollow noreferrer">http://computer.howstuffworks.com/question697.htm</a> for a little description of why its very, very difficult to get complete randomness form a computer.</p>\n'}, {'answer_id': 66651, 'author': 'Paul Reiners', 'author_id': 7648, 'author_profile': 'https://Stackoverflow.com/users/7648', 'pm_score': 3, 'selected': True, 'text': '<p>You could use the <a href="http://en.wikipedia.org/wiki/Knuth_shuffle" rel="nofollow noreferrer">Fisher-Yates shuffle</a>.</p>\n'}, {'answer_id': 66688, 'author': 'Scott Swezey', 'author_id': 9439, 'author_profile': 'https://Stackoverflow.com/users/9439', 'pm_score': 0, 'selected': False, 'text': "<p>Short Answer: PHP's <code>array_rand()</code> function</p>\n\n<p>Given that the use of the shuffle function is forbidden, I would use <code>$keys = array_rand($myArray, count($myArray))</code> to return an array of the keys from <code>$myArray</code> in random order. From there it should be simple to reassemble them into a new array that has been randomized. Something like: </p>\n\n<pre><code>$keys = array_rand($myArray, count($myArray));\n$newArray = array();\n\nforeach ($keys as $key) {\n$newArray[$key] = $myArray[$key];\n}\n</code></pre>\n"}, {'answer_id': 66754, 'author': 'Community', 'author_id': -1, 'author_profile': 'https://Stackoverflow.com/users/-1', 'pm_score': 1, 'selected': False, 'text': '<p>He\'s probably testing you on a relatively common mistake most people make when implementing a shuffling algorithm (this was also actually at the center of a <a href="http://itmanagement.earthweb.com/entdev/article.php/11070_616221_2" rel="nofollow noreferrer">controversy</a> involving an online poker site a few years back)</p>\n\n<p>Incorrect way to shuffle:</p>\n\n<p><code>\nfor (i is 1 to n)\n  Swap i with random position between 1 and n \n</code></p>\n\n<p>Correct way to shuffle:</p>\n\n<p><code>\nfor (i is 1 to n)\n  Swap i with random position between i and n\n</code></p>\n\n<p>Graph out the probability distribution for these cases and it\'s easy to see why the first solution is incorrect.</p>\n'}, {'answer_id': 66805, 'author': 'fixedd', 'author_id': 9557, 'author_profile': 'https://Stackoverflow.com/users/9557', 'pm_score': 2, 'selected': False, 'text': '<p>Well here\'s the solution I came up with:</p>\n\n<pre><code>function randomize_array_1($array_to_randomize) {\n    $new_array = array();\n    while (count($array_to_randomize) &gt; 0) {\n        $rand_num = rand(0, count($array_to_randomize)-1);\n        $extracted = array_splice($array_to_randomize, $rand_num, 1);\n        $new_array[] = $extracted[0];\n    }\n    return $new_array;\n}\n</code></pre>\n\n<p>And here\'s his solution:</p>\n\n<pre><code>function randomize_array_2($array_to_randomize) {\n    usort($array_to_randomize, "rand_sort");\n    return $array_to_randomize;\n}\nfunction rand_sort($a, $b) {\n    return rand(-1, 1);\n}\n</code></pre>\n\n<p>I ran a bunch of trials on both methods (trying each 1,000,000 times) and the speed difference was negligible. However, upon checking the actual randomness of the results I was surprised at how different the distributions were. Here\'s my results:</p>\n\n<pre><code>randomize_array_1:\n    [2, 3, 1] =&gt; 166855\n    [2, 1, 3] =&gt; 166692\n    [1, 2, 3] =&gt; 166690\n    [3, 1, 2] =&gt; 166396\n    [3, 2, 1] =&gt; 166629\n    [1, 3, 2] =&gt; 166738\n\nrandomize_array_2:\n    [1, 3, 2] =&gt; 147781\n    [3, 1, 2] =&gt; 73972\n    [3, 2, 1] =&gt; 445004\n    [1, 2, 3] =&gt; 259406\n    [2, 3, 1] =&gt; 49222\n    [2, 1, 3] =&gt; 24615\n</code></pre>\n\n<p>As you can see, the first method provides an almost perfect distribution indicating that it\'s being more-or-less truly random, whereas the second method is all over the place.</p>\n'}]
['https://Stackoverflow.com/questions/65970', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/9557/']