Trier un tableau aléatoirement

Il y a quelques temps, j’ai été confronté au besoin de trier les éléments d’un tableau de manière aléatoire. En général, on trie pour ordonner les éléments et pour cela, il existe de nombreux algorithmes et, nativement, la plupart des langages implémentent des méthodes basique de tri.

En javascript par exemple, en passant une fonction de tri à la méthode sort de l’objet Array on peut aisément trier un tableau. Mais pour trier aléatoirement les éléments d’un tableau, ça ne peut pas fonctionner.

En effet, la méthode que l’on passe en paramètre de sort doit fournir un résultat constant quelque soit les éléments que l’on compare. Ce qui n’est pas le principe de l’aléatoire.

En recherchant, j’ai vu plusieurs façon de faire et celle qui m’a le plus plu/convaincu est l’algorithme de Fisher-Yates.

Et j’ai également trouvé une implémentation de cet algorithme par Mike Bostock que je recopie ci-dessous :

function shuffle(array) {
  var m = array.length, t, i;
  // While there remain elements to shuffle…
  while (m) {
    // Pick a remaining element…
    i = Math.floor(Math.random() * m--);
    
    // And swap it with the current element.
    t = array[m];
    array[m] = array[i];
    array[i] = t;
  }

  return array;
}

(Note: originellement publié sur pprb.dev)

Laisser un commentaire

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.