Randomly Shuffling the Order of Elements in an Array
2012-05-24
Introduction
Recently I needed to write a function that took an array of objects and randomly sorted or 'shuffled' the order of the objects. After coding up what appeared to be the most straight-forward solution, I discovered that the algorithm I used did not actually work correctly.
In this article I will show a correct solution for shuffling an array using the Fisher-Yates algorithm. I will present example code in several programming languages.
The Wrong Way to Do It
My first attempt at solving this problem was to try the following:
function broken_shuffle(a) { a.sort(function () { return Math.floor(Math.random() - 0.5); }); }
It turns out, because of the algorithm that JavaScript uses to implement its sorting function, the code above will not produce a truely randomly ordered array. The items in the array will be shuffled around a bit, but will be more likely to be close to their original positions.
Searching on the web for 'javascript random order array' will result in many pages that show this incorrect solution, demonstrating why you should be very careful about where you get your information!
Fisher-Yates Shuffle
One correct way to randomly shuffle the order of elements in an array is to use the Fisher-Yates shuffle algorithm.
The following JavaScript code demonstrates how to use the Fisher-Yates algorithm to shuffle the elements in an array.
// Fisher-Yates shuffle function shuffle(a) { var i = a.length - 1; var j, temp; while (i > 0) { j = Math.floor(Math.random() * (i + 1)); temp = a[i]; a[i] = a[j]; a[j] = temp; i = i - 1; } }
Demo
The following animated JavaScript demo shows a set of numbers being shuffled using the Fisher-Yates algorithm:
Green = shuffled elements
Yellow = random element selected from the remaining unshuffled elements
Other Programming Languages
Perl/PHP
In Perl or PHP, the shuffle algorithm can be written:
# Fisher-Yates shuffle sub shuffle { my $i = scalar(@_) - 1; my $j; my $temp; while ($i > 0) { $j = int(rand($i + 1)); $temp = $_[$i]; $_[$i] = $_[$j]; $_[$j] = $temp; $i = $i - 1; } }
C, C++ and Java
In C or C++ programming languages, the shuffle algorithm can be written:
// Fisher-Yates shuffle #include <time.h> #include <stdlib.h> void shuffle(int * a, int n) { int i = n - 1; int j, temp; srand(time(NULL)); while (i > 0) { j = rand() % (i + 1); temp = a[i]; a[i] = a[j]; a[j] = temp; i = i - 1; } }
The C/C++ code can also be simply modified to work in Java.