Skip to content

Instantly share code, notes, and snippets.

@gubatron
Created February 24, 2012 03:22
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save gubatron/1897094 to your computer and use it in GitHub Desktop.
Save gubatron/1897094 to your computer and use it in GitHub Desktop.
How to shuffle a list in javascript in O(n) time using the Fisher-Yates algorithm
/**
* Returns number starting from offset up to n-1
*/
function getRandomWithOffset(n,offset) {
return Math.floor(Math.random()*n+offset);
}
/**
* Returns random integer from 0 to n-1
*/
function getRandom(n) {
return getRandomWithOffset(n,0);
}
/** Fisher–Yates shuffle algorithm O(n) */
function shuffleList(list) {
for (var i=list.length-1; i>0; i--) {
var j = getRandom(i+1);
var buffer = list[i];
list[i]=list[j];
list[j]=buffer;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment