Randomizing Javascript Arrays


An array in JavaScript is like a collection of data. When one variable usually stores one value, an array stores multiple values. Each value is associated with an index position, otherwise known as ‘array key’. If you would like to learn more about arrays and how they work, read this article: https://developer.mozilla.org/en/JavaScript/Reference/Global_Objects/Array

If an array were a deck of cards, one might say that we need to “shuffle the deck”. That’s exactly what we need to do in this situation, but it’s better referred to as “sorting the array”. We need to change the order that the array is sorted in. The Array data type is really an object in JavaScript, and like most objects, it comes pre-built with methods (functions) that we can take advantage of. One method of interest is ‘sort’.

The Array’s ‘sort’ method accepts a callback function as an argument and uses it to compare the data inside the array. A callback function is a reference to a function that can be executed at a later time in your code. This can be better referred to as a ‘compare function’, because that’s what it’s there for, to compare the data. When executed, the ‘compare function’ is passed two valus from the array. If the ‘compare function’ is not provided, the array will be sorted in alphabetical order. See this website for detailed information on the Array’s ‘sort’ method: https://developer.mozilla.org/en/JavaScript/Reference/Global_Objects/Array/sort.

The idea is, you compare the data that gets passed to the ‘compare function’ and return a numerical value. The array gets sorted based on the values you return. The values can be less than 0, greater than 0, or exactly 0. Each value has special importance for how the data gets sorted. So, basically, we need a random number that meets this definition. For this, we use Math.random().

Math.random() returns a random number between 0 and 1. This is almost perfect, but we miss an entire number range, less than 0. Since the value from Math.random() could be 0.12, or 0.5, or 1, or even 0, we can subtract 0.5 from it to include the negative numbers in our range, and we still have the possibility of getting 0 or a value greater than 0. And so we have the following code:

?View Code JAVASCRIPT
var my_array = ['one','two','three'];
 
my_array.sort(function(){
	return Math.round(Math.random()) - 0.5;
});

A Not So Shuffled Array

At a glance, this looks like it should be perfect for what we need. When observed more carefully, though, we find inconsistancies in how the items actually get shuffled. This is due to the way the ‘sort’ method actually works. It’s based off the Bubble Sort algorithm. The bubble sort says, if A < B and B < C then there's no need to compare A and C. Because of this, some items may not actually get shuffled, and we end up with a not so shuffled array.

Fisher-Yates Shuffle

In 1938, two men known as Ronald Fisher and Frank Yates, outlined a way to randomize a list of numbers. We refer to it now as, the Fisher-Yates Shuffle. This method was released in their book, Statistical tables for biological, agricultural and medical research, and was designed to be implemented using pencil and paper. The method worked like this:

  1. Write down the numbers from 1 to N
  2. Pick a random number, k, between one and the number of unstruck numbers remaining (inclusive)
  3. Counting from the low end, strike out the kth number not yet struck out, and write it down elsewhere.
  4. Repeat from step 2 until all the numbers have been struck out.

Knuth Shuffle

If you were going to code the Fisher-Yates Shuffle using JavaScript, you would most likely model it off what we know as the Knuth Shuffle. In 1964, Richard Durstenfeld modernized the Fisher-Yates Shuffle for computer use in his book, Communications of the ACM, volume 7. This modernization was made popular as the Knuth Shuffle, by Donald E. Knuth, in volume 2 of his book, The Art of Computer Programming.

This approach is a little more difficult to implement than using ‘sort’, but the results are worth it. It works by looping the array backwards, and each time through, swapping the current item with a random item. The range that it uses to generate a random number follows the rule, 0 <= random number <= current index. If given an array with 4 items, the 4th item in the array will be swapped with an item at index positions 0, 1, or 2. The 3rd item will be swapped with the item at index positions 0 or 1. The 2nd item won't actually be so random, it will swap with the item at index position 0, the first item. At this point, the first item may or may not have already been swapped. By the time the fourth iteration occurres, all of the items in the array should have been shuffled, so it only loops n - 1 times, where 'n' represents the amount of items in the array. Here's what it looks like in JavaScript. I've attached it to the Array's prototype object so that every array has access to it.

?View Code JAVASCRIPT
Array.prototype.randomize = function()
{
	var i = this.length, j, temp;
	while ( --i )
	{
		j = Math.floor( Math.random() * (i - 1) );
		temp = this[i];
		this[i] = this[j];
		this[j] = temp;
	}
}
 
var my_array = ['one','two','three'];
my_array.randomize();

Contrasted Example

View: Live Example.

VN:F [1.9.22_1171]
Rating: 9.6/10 (16 votes cast)
VN:F [1.9.22_1171]
Rating: +4 (from 4 votes)
Randomizing Javascript Arrays, 9.6 out of 10 based on 16 ratings
Share/Save

  1. #1 by asaavedra78 on October 1, 2010 - 6:01 pm

    Nicely done…again.

    VA:F [1.9.22_1171]
    Rating: 0.0/5 (0 votes cast)
    VA:F [1.9.22_1171]
    Rating: +1 (from 1 vote)
(will not be published)