happyworm/jPlayer — pull request #205 by lusaisai (2014-04-19 16:00:03+00:00)
Title: update shuffle algorithm for add-on/jplayer.playlist.js

Hi All

I've been using the jplayer.playlist.js add-on for a while, and I realized the shuffle function does not work very well, the shuffle results look similar from shuffles to shuffles.
So I look into the code to see where the problem is and draft out a version according to [Fisher–Yates shuffle](http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm), you may have a review to see if such a change/idea can be incorporated into your code.

Below are the analysis I've done,

Here's the current shuffle way, it depends on the the built-in array sort method.
```javascript
self.playlist.sort(function() {
return 0.5 - Math.random();
});
```
I ran the shuffle several times, the list is not well shuffled, it even didn't change after one shuffle, see below console output,
```javascript

var list = [1,2,3,4,5,6,7,8,9];

list.sort(function() {
return 0.5 - Math.random();
});
[1, 2, 7, 6, 8, 4, 5, 3, 9]
list.sort(function() {
return 0.5 - Math.random();
});
[2, 1, 8, 7, 4, 9, 6, 5, 3]
list.sort(function() {
return 0.5 - Math.random();
});
[2, 1, 8, 7, 4, 9, 6, 5, 3]
list.sort(function() {
return 0.5 - Math.random();
});
[1, 2, 8, 9, 3, 4, 7, 6, 5]
list.sort(function() {
return 0.5 - Math.random();
});
[4, 1, 2, 8, 3, 9, 5, 6, 7]
```

There could be different sort algorithm implementations based on different vendors, array size, etc. I tested a small array on chrome, it looks like chrome is using insertion sort in this case.
```javascript
var list = [3,2,1];

list.sort(function(a,b) {
console.log(list);
console.log('compare ' + a + ' and ' + b);
return a - b;
});
[3, 2, 1]
compare 3 and 2
[2, 3, 1]
compare 3 and 1
[2, 3, 3]
compare 2 and 1
[1, 2, 3]
```
Thus, in case of insertion sort, the steps are,
1. the first item is already sorted
2. compare the second with first, if the order is wrong, move first item one place right and insert the second item at place one, based on the current shuffle function, there are 50% possibility that there order won't change.
3. compare the third with previous two one by one, insert it at the right place, based on the current shuffle function, there are 50% possibility that there order won't change.
4. and so on...

This is what I think caused the shuffle not working well.

The updated version works better,
```javascript
var arrayShuffle = function (array) {
var valueSwap = function(array, i , j) {
var tmp = array[i];
array[i] = array[j];
array[j] = tmp;
};

var getRandomInt = function(min, max) {
return Math.floor(Math.random() * (max - min + 1)) + min;
};

for (var i = 0; i < array.length - 1; i++) {
var j = getRandomInt(i + 1, array.length - 1);
valueSwap(array, i, j);
};

return array;
};

var list = [1,2,3,4,5,6,7,8,9];

arrayShuffle(list);
[7, 1, 2, 3, 6, 8, 9, 4, 5]
arrayShuffle(list);
[6, 2, 4, 5, 8, 3, 1, 7, 9]
arrayShuffle(list);
[2, 7, 5, 1, 3, 9, 6, 8, 4]
arrayShuffle(list);
[9, 3, 6, 5, 8, 4, 2, 1, 7]
arrayShuffle(list);
[2, 6, 7, 9, 5, 1, 3, 8, 4]
```

Thanks
lusaisai