Après que Jon a déjà couvert la théorie, voici une mise en œuvre:
function shuffle(array) {
var tmp, current, top = array.length;
if(top) while(--top) {
current = Math.floor(Math.random() * (top + 1));
tmp = array[current];
array[current] = array[top];
array[top] = tmp;
}
return array;
}
L'algorithme est - O(n), alors que le tri doit être O(n log n). En fonction de la surcharge de l'exécution de code JS par rapport aux natifs sort() de la fonction, cela pourrait conduire à une notable différence dans la performance, ce qui devrait augmenter avec la taille des matrices.
Dans les commentaires à bobobobo de réponse, j'ai dit que l'algorithme en question peut ne pas produire uniformément répartie probabilités (en fonction de la mise en œuvre de l' sort()).
Mon argument va dans ce sens: Un algorithme de tri nécessite un certain nombre c de comparaisons, par exemple, c = n(n-1)/2 pour Bubblesort. Au hasard de notre fonction de comparaison rend le résultat de chaque comparaison tout aussi probable, c'est à dire il y a 2^c également probables résultats. Maintenant, chaque résultat doit correspondre à l'une des n! permutations de la matrice des entrées, ce qui rend une même distribution de l'impossible dans le cas général. (C'est une simplification, comme le nombre de comparaisons neeeded dépend du tableau d'entrée, mais l'affirmation devrait encore tenir.)
Comme Jon l'a souligné, cela seul n'est pas une raison pour préférer de Fisher-Yates sur l'aide d' sort(), comme le générateur de nombre aléatoires carte en un nombre fini de nombres pseudo-aléatoires les valeurs de l' n! permutations. Mais les résultats de Fisher-Yates devrait être encore mieux:
Math.random() génère un nombre pseudo-aléatoire dans l'intervalle [0;1[. Comme JS utilise la virgule flottante en double précision des valeurs, ce qui correspond à 2^x valeurs possibles où 52 ≤ x ≤ 63 (je suis trop paresseux pour trouver le nombre). Une distribution de probabilité généré à l'aide d' Math.random() va cesser de se comporter ainsi, si le nombre d'événements atomiques est du même ordre de grandeur.
Lors de l'utilisation de Fisher-Yates, le paramètre pertinent est la taille de la matrice, ce qui ne doit jamais s'approcher 2^52 en raison de limitations pratiques.
Lors du tri avec un nombre aléatoire de comparaison de la fonction, la fonction fondamentalement importe seulement si la valeur de retour est positif ou négatif, de sorte que ce ne sera jamais un problème. Mais il y a un similaire: Parce que la fonction de comparaison est bien comporté, l' 2^c résultats possibles sont, comme indiqué, tout aussi probable. Si c ~ n log n alors 2^c ~ n^(a·n) où a = const, ce qui le rend au moins possible qu' 2^c est de même ordre de grandeur que (ou même moins) n! et conduisant ainsi à une distribution inégale, même si l'algorithme de tri où la carte sur le permutaions uniformément. Si cela a un impact au-delà de moi.
Le vrai problème est que les algorithmes de tri ne sont pas garanties à la carte sur les permutations de manière homogène. Il est facile de voir que Mergesort fait comme il est symétrique, mais le raisonnement à propos de quelque chose comme Bubblesort ou, plus important encore, Quicksort ou Heapsort, ne l'est pas.
La ligne du bas: tant Que sort() utilise Mergesort, vous devriez être raisonnablement sûr, sauf en cas de coin (au moins j'espère qu' 2^c ≤ n! est un coin de cas), si ce n'est, tous les paris sont éteints.
