Algorithmes de Tri pour Débutants en JavaScript : Bulle, Sélection et Tri par Insertion

Disposer de vos ensembles de données disposés bon gré mal gré ne fera qu’ajouter plus de temps et de ressources à gérer et à rechercher. Que vos données soient triées ou non affectera directement les méthodes de recherche que vous pouvez utiliser et peut faire la différence entre une recherche prenant un million d’opérations ou en prenant 10, comme avec la recherche binaire.

Par souci de simplicité, nous allons nous concentrer uniquement sur le tri d’un tableau de nombres du plus petit au plus grand, mais ces algorithmes sont facilement modifiables pour d’autres objectifs de tri. Gardez à l’esprit qu’il s’agit de concepts et de modèles plus généraux et moins d’un « mode d’emploi » pour trier les données, car votre implémentation particulière peut différer beaucoup, mais à la fin, elle peut ressembler conceptuellement à ces modèles.

Voici le tableau de pratique de 50 nombres aléatoires.

const unsortedArr = ;

Prérequis

Je vais tout regarder à travers l’objectif de la notation Big O, donc comprendre comment la complexité augmente avec le temps sera très utile.

Tri à bulles

C’est le « Hello World » des méthodes de tri, rien de fou mais ça fait le travail.

Pour chaque élément du tableau, nous voulons vérifier si l’élément suivant est plus grand, s’il est ensuite échangé leurs index dans le tableau. Pour éviter de recomparer des nombres triés, nous commencerons par l’arrière du tableau tandis qu’un autre for loop obtiendra le nombre précédent. De cette façon, toutes les plus grandes valeurs s’accumulent, ou « bouillonnent », à la fin.

 Animation de tri de bulles

Graphique / Animation grâce à VisuAlgo.net

Notre version fonctionne à l’envers à partir de l’animation, mais elle est assez proche.

const bubble = arr => { const swap = (list, a, b) => , list] = , list]; for (let i = arr.length; i > 0; i--) { for (let j = 0; j < i - 1; j++) { if (arr > arr) swap(arr, j, j + 1); }; }; return arr;};console.log(bubble(unsortedArr));

Tri de sélection

Le tri de sélection fonctionne comme le contraire du tri à bulles, tandis que le tri à bulles pousse toutes les valeurs les plus grandes jusqu’à la fin maintenant, nous allons pousser les valeurs minimales au début.

Chaque fois qu’il boucle sur le tableau, il sélectionne la plus petite valeur, s’il trouve une valeur inférieure qui devient alors la nouvelle valeur la plus basse. Lorsque la boucle est terminée, elle prendra ce minimum et le placera à l’avant du tableau avant de recommencer la boucle. De cette façon, la valeur la plus basse de chaque itération est empilée sur le devant jusqu’à ce que le tableau entier soit trié.

 Sélection Trier l'animation

Graphique / Animation grâce à VisuAlgo.net

const selection = arr => { const swap = (list, a, b) => , list] = , list]; arr.forEach((item, i) => { let min = i; for (let j = i + 1; j < arr.length; j++) { if (arr < arr) min = j; }; swap(arr, i, min); }); return arr;};console.log(selection(unsortedArr));

Tri par insertion

Mon préféré et le plus performant des trois, le tri par insertion, est plus similaire à la façon dont vous trieriez quelque chose à la main.

Nous considérons le tableau comme deux parties, la triée et la non triée, avec chaque fois que nous trouvons une nouvelle valeur, nous revenons en boucle pour trouver sa place dans la moitié triée. Avec chaque ajout, notre groupe trié se développe jusqu’à ce qu’il soit l’ensemble du tableau.

 Animation de Tri par insertion

Graphique / Animation grâce à VisuAlgo.net

const insertion = arr => { arr.forEach((item, i) => { let num = arr; let j; for (j = i - 1; j >= 0 && arr > num; j--) { arr = arr; }; arr = num; }); return arr;};console.log(insertion(unsortedArr));

Comparaison

Un problème avec l’utilisation de la notation Big O pour comparer les algorithmes est qu’elle est basée sur le scénario du pire, qui peut être le même entre les algorithmes donnant la fausse illusion qu’ils sont égaux. Bien que les types de bulles, de sélection et d’insertion soient tous O (n ^ 2), cela ne nous dit pas grand-chose sur le scénario moyen ou le meilleur des cas ou sur la façon dont ils varient avec la structure de données.

Le tri par insertion gagne à chaque fois. Il a également l’avantage de ne pas avoir besoin d’avoir l’ensemble du tableau avant de commencer, ce qui vous permet de trier les choses en temps réel au fur et à mesure que les données entrent.

Gardez cela à l’esprit car vous ne devez pas décider quel algorithme est le « meilleur » avant de considérer comment vos données sont déjà organisées.

Conclusion

Ces trois solutions sont loin d’être les meilleures pour trier efficacement de grandes quantités de données, mais elles sont parmi les plus intuitives pour plonger vos orteils dans ce qui peut être un océan écrasant. 🌊