Created
February 24, 2012 03:22
-
-
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* 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