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:

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.