Fisher Yates Shuffle Modern Algorithm Array Programming Tutorial
In this programming exercise we will demonstrate the concepts behind the Fisher-Yates Modern Shuffle algorithm because we are going to be using its logic to program a shuffle method into JavaScript. Using a physical example on the table we will convey the logic behind the algorithm and discuss the concept, then we will write the logic in JavaScript programming to add an array shuffle method to JavaScript's array object.
Basic example
var arr = ['A','B','C','D','E','F','G','H'];
var i = arr.length, j, temp;
while(--i > 0){
j = Math.floor(Math.random() * (i+1)); // Get random number ranging between 0 and i
temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
document.write(arr);
Extend JavaScript by creating a shuffle method for the Array object
Array.prototype.shuffle = function(){
var i = this.length, j, temp;
while(--i > 0){
j = Math.floor(Math.random() * (i+1));
temp = this[j];
this[j] = this[i];
this[i] = temp;
}
return this;
}
var arr = ['A','B','C','D','E','F','G','H'];
var result = arr.shuffle();
document.write(result);
Developer notes and display for seeing the loop actions each pass
<p>The loop should iterate over the array from back to front bypassing index 0. The loop should run (array.length - 1) times.</p>
<p>Each loop pass generate a random number ranging between 0 and i.</p>
<p>Each loop pass Swap index i value with value found at index j</p>
<p id="dev"></p>
<script>
var arr = ['A','B','C','D','E','F','G','H'];
var dev = document.getElementById('dev');
var i = arr.length, j, temp;
while(--i > 0){
dev.innerHTML += "Affecting index position "+i+" of the array";
dev.innerHTML += " --- Generate a random number ranging between 0 and "+i;
j = Math.floor(Math.random() * (i+1)); // Get random number ranging between 0 and i
dev.innerHTML += " --- Generated: "+j;
dev.innerHTML += " --- Swap values found at index "+i+" and index "+j+"<br>";
temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
document.write(arr);
</script>