Technique #1
function Shuffle(o) {
for(var j, x, i = o.length; i; j = parseInt(Math.random() * i), x = o[--i], o[i] = o[j], o[j] = x);
return o;
};
Usage
var testArray = [1,2,3,4,5];
Shuffle(testArray);
// jQuery to dump out new values to element with ID of 'dump'
$(function() {
for (var i=0;i<testArray.length;i++) {
$("#dump").append(testArray[i]);
}
});
Technique #2
yourArray.sort(function() { return 0.5 - Math.random() });
Nice.. this code snippet helped me a lot! Thanks :)
Technique #2
yourArray.sort(function() { return 0.5 – Math.random() });
This is very helpful for me also thank you.
+1 for the .sort() method in Technique #2! very clever…
Hey, once again absolutely helpful, really glad to see that apart from a really good CSS resource, CSS-tricks is great as a JS asset as well!!
thanks!!
Hey,
Very usefull! thanks! 1 question, can you explain me what technique 2 does?
Especially the { return 0.5 – Math.random() });. How does this sort the array?
Greetz
I’ll try my hand at explaining it.
The sort function allows you to pass a compare function to it, what that function returns then sorts the object in the array.
So if it returns
-1
then object A will be given a lower index than B.0
will leave their order the same, and1
will give B a lower index than A. That is what I can figure from the documentation.But how does this apply to the code provided ?
Math.random()
returns a random number between 0 and 1. So putting in the0.5 - Math.random()
you will get a number between -1 and 1, which is what the sort function needs.So each object in the array is given a random index number and then sorted by that index.
I could be wrong, I most likely am, but that is how I can interpret it. I’m 100% on the
0.5 - Math.Random
part, but thesort
function is where I am not completely certain.But hey it works right ?
How this works is like follows:
When such a function is passed into array.sort(), the array elements are sorted based on the relationship between each pair of elements “a” and “b” and the function’s return value. The three possible return numbers are: 0 (greater than 0):
Less than 0: Sort “a” to be a lower index than “b”
Zero: “a” and “b” should be considered equal, and no sorting performed.
Greater than 0: Sort “b” to be a lower index than “a”
When you do Math.random() it returns a random number between 0 and 1. So in 50% of the cases, the 0.5 in the above case will be smaller than the Math.random() number and in the other half of the cases, it will be larger. When it is smaller, the sort order will be ascending, when it is larger, the sort order will be descending. That leads to a random sort order of the array.
Do no use the Array.sort() technique! It’s doesn’t perform randomised shuffling. The Fisher-Yates algorithm, implemented in the first technique, is the way to go. The link below shows a cleaner implementation of this algorithm, and explains why the Array.sort() technique is wrong.
http://sroucheray.org/blog/2009/11/array-sort-should-not-be-used-to-shuffle-an-array/
You is a genius !!!! Thanks!
You is a genius !!!! Thanks!
http://eagle-design.ir/
Thanks for this Chris, I borrowed your Shuffle technique to make this card game demo:
http://codepen.io/bitmapshades/pen/raOZMa
Happy Crimbo!
The version using sort should be avoided. You can easily observe that it rarely shuffles the last elements enough (they are often left in the same place).
The reason for sort being a bad idea is – sort is optimized to sort an array according to your wishes (the function you provide). The function you provide is actually meant to take two arguments (two elements from the array). You are supposed to compare them in the function and return -1 if the first one should be sorted before the second one, 1 if the second one should be sorted before the first one and 0 if they are equal…)
So sort is a brilliant method since you can provide your own logic for ordering an array by the function you give it. You are in control of how you want things ordered.
And JavaScript is in control of how many times your function is called and with which elements from the array – the JS engine aims to call it as few times as possible, just enough to decide the correct sorting order. Then it stops calling sort. That way sorting an array takes as little time as possible.
But when you ignore comparing elements and just return a random number, the JS engine still tries to minimize calls – so most sequences of random -1 and 1 values makes it conclude that is has done all necessary sorting LONG BEFORE all elements have been shuffled around.
So: Please use sort for sorting things in an ordered nice way according to logic rules. But DON’T use it to shuffle an array! :D
A more theoretical explanation (and measurements) can be found here:
http://www.robweir.com/blog/2010/02/microsoft-random-browser-ballot.html
If you are looking for something that does not destroy the original array but gives you a shuffled copy, you can use something like
Array.prototype.shuffle = function(){
var x = this.slice(), y = [];
while(x.length){y.push(x.splice(Math.floor(Math.random()*x.length),1)[0]);}
return y;
}
Now all arrays can be shuffled like
var a = [1,2,3,4,6,7,8];
console.log( “Shuffle 1”, a.shuffle() );
console.log( “Shuffle 2”, b.shuffle() );
etc.
Speed comparison
https://jsperf.com/array-shuffe-test
Technique #2 is not working!
http://codepen.io/GottZ/pen/ZbEaZg
Statistically speaking, the swap inside sort would happen only half the time when it is “needed” and as a result you would have a bias towards the original values.
What if we changed the code to: “yourArray.sort(function() { return Math.random() – Math.random() });”? Would it eliminate the bias?
var arr = [1, 2, 3, 4];
function Shuffle(a){for(var b,c,d=a.length; d>0;)c=Math.floor(Math.random()*d),d–,b=a[d],a[d]=a[c],a[c]=b;return a;}
for(i=0;i<100;i++){
document.write(Shuffle(arr)+””);
}
THis Is a Cipher For Alphanumeric chars that changes every time you run the code like rot13. I call It Rot-Rand.
The second technique seems very elegant and clever.
I’m still concerned about what will happen if the web browser implements the sorting algorithm using BubbleSort or QuickSort…
It seems that for some sorting algorithms there is no problem, but for others, it could make them run forever, as they’ll almost never get a series of “correct” responses, as it’s probability is exponentially tends to 0.
Awesome ! That save me ! thank you a lot :)