✅ Algorithmes de tri JavaScript simples

Table des matières

Un algorithme est par définition un ensemble ordonné (C'est très important) d'opérations systématiques qui nous permet de faire un calcul pour trouver la solution de tous les problèmes du même type. En d'autres termes, il s'agit d'un ensemble d'instructions qui suit toujours le schéma suivant :

Précision: Vous devez expliquer de manière unique et sans équivoque chaque étape ou instruction.
Fini: Le nombre d'instructions à exécuter doit être limité.
Définition: Les mêmes données d'entrée doivent toujours fournir les mêmes informations de sortie.
Entrée: Le nombre d'éléments d'entrée peut être nul ou supérieur.
Résolution: Il doit toujours produire un résultat, qui sera la ou les données de sortie.

Lorsqu'un algorithme est implémenté dans un certain langage de programmation, il devient un programme qui peut être exécuté sur un ordinateur, on peut donc dire qu'un programme est un algorithme ou un ensemble d'algorithmes écrits dans un langage spécifique que l'ordinateur peut interpréter. Dans ce cas, ce programme est appelé un algorithme de calcul. En revanche, s'il n'a pas besoin d'ordinateur pour fonctionner, on parle d'algorithmes non informatiques.

Dans notre cas, nous allons parler de algorithmes de calcul.

Sachant ce qu'est un algorithme, nous allons nous concentrer sur les algorithmes de tri, ou ce qui est le même, l'algorithme qui sert à trier et retourner une liste qui a été initialement fournie avec des éléments placés aléatoirement déjà ordonnés.
Les 3 algorithmes de tri les plus connus sont Tri par bulle ou tri par bulle, Tri par sélection ou tri par sélection et Tri ou tri par insertion par insertion. Tous sont considérés comme des algorithmes ou des méthodes simples car ils sont résolus par itération ou répétition jusqu'à un nombre n de fois.

1. Tri par bulle ou tri par bulleEn prenant comme exemple un tableau à quatre valeurs, dans ce cas pour simplifier quatre nombres nous verrons comment fonctionne l'algorithme.

Tableau = (4, 7, 8, 5, 9);

Nous souhaitons que vous le renvoyiez classé du plus haut au plus bas par exemple, soit (9, 8, 7, 5, 4).

Pour ce faire, la première chose que nous devons faire est de demander les deux premières valeurs qui est la plus grande. Dans le cas où la deuxième valeur est supérieure à la première, comme c'est le cas, ils doivent être échangés, en revanche, s'ils sont déjà commandés, nous les laissons tels quels.
Ensuite, le même processus devrait être répété avec les deuxième et troisième valeurs. Dans ce cas, la troisième valeur est plus grande, nous l'échangerions, laissant notre tableau = (7, 8, 4, 5, 9).
Ensuite, nous répétons l'étape précédente avec les troisième et quatrième valeurs, et à nouveau nous les échangeons. (7, 8, 5, 4, 9).
Et enfin après la première itération ce serait : (7, 8, 5, 9, 4).
Il n'est toujours pas ordonné, cependant il n'a été réalisé que le dernier élément, celui à droite de l'ensemble, le 4, s'il est ordonné comme le plus petit nombre de tous.
Au tour suivant pour ordonner notre tableau, il n'est plus nécessaire de prendre en compte le dernier car on sait déjà qu'il est ordonné, donc on comparerait le premier et le deuxième élément, puis le deuxième et le troisième élément, et enfin le troisième et quatrième élément et le tableau resterait : ( 8, 7, 9, 5, 4).
Maintenant, le dernier et l'avant-dernier élément sont triés.
Nous effectuons un autre tour en comparant les première et deuxième valeurs, puis les deuxième et troisième et le tableau ressemble à ceci : (8, 9, 7, 5, 4).
Les trois derniers éléments sont déjà ordonnés, il ne faut donc qu'un tour de plus pour laisser le tableau complètement ordonné : (9, 8, 7, 5, 4).

C'est ainsi que le algorithme de burburja, qui s'appelle ainsi parce qu'à chaque tour le dernier élément monte comme une bulle et est ordonné.

Maintenant mis en œuvre pour JavaScript c'est très simple:

bulle de fonction (monTableau) {var tam = monTableau.length; for (var temp = 1; temp <size; temp ++) {for (var left = 0; left <(size - temp); left ++) {var right = left + 1; if (monTableau [gauche] <monTableau [droite] {sort (monTableau, gauche, droite);}}} return monTableau;}

Nous passons un tableau à notre fonction et à l'intérieur de celui-ci, la première chose que nous faisons est de calculer sa taille, de calculer le nombre d'éléments dans le tableau.
Ensuite, nous créons une boucle externe qui parcourt notre tableau autant de fois que les éléments ont moins un (puisque ce sont les temps nécessaires pour qu'il soit complètement commandé).
En interne, nous créons une autre boucle qui parcourt les valeurs en comparant chacune avec la suivante et si celle de gauche est inférieure à celle de droite, elle les échange avec la fonction de tri que nous verrons ensuite.
Enfin, il renvoie le tableau ordonné.

fonction tri (monTableau, valeur1, valeur2) {var temp = monTableau [valeur1]; monTableau [valeur1] = monTableau [valeur2] ; monTableau [valeur2] = temp; renvoie monTableau ;}

où valeur1 est l'indice du premier article à échanger et valeur2 est l'indice du deuxième article à échanger.

2. Tri par sélectionL'algorithme que nous verrons ci-dessous ne déplace pas les éléments un par un comme dans la bulle, mais parcourt d'abord le tableau complet, puis sélectionne l'élément correct pour le placement en fonction des critères que nous suivons (par exemple, du plus haut au plus bas) et il le place directement dans sa position, et c'est ainsi que l'algorithme tire son nom, sélectionnant, prenant un élément et le déplaçant d'un seul mouvement jusqu'à sa position correcte.

Dans le même exemple que précédemment Array = (4, 7, 8, 5, 9) si nous voulons l'ordonner du plus haut au plus bas par exemple, nous sélectionnerions d'abord 9 et le mettrons à la première place et 4 occuperait le dernier position (9, 7, 8, 5, 4). Au deuxième tour, il choisirait le 8 et l'échangerait avec le 7 pour rester dans la bonne position. Dans les tours suivants, je ne modifierais rien car il a déjà été commandé.

Le code de cet algorithme serait le suivant :

sélection de fonction (monTableau) {var tam = monTableau.length; for (var temp = 0; temp <taille -1; temp ++) {major = temp; for (var check = temp + 1; check <size; check ++) {if (myArray [check] <myArray [major] {major = check;}} sort (myArray, major, check);} return myArray;}

Le code fonctionne de manière similaire à celui de la bulle mais la boucle for externe passe par les valeurs de 0 à N-2 (ce sont le même nombre de pas qu'entre 1 et N-1 que dans la bulle mais le fonctionnement est différent ) agissant directement sur les éléments pour les amener à la bonne position à chaque tour.
Le nombre de tours nécessaires pour que tous les éléments soient commandés est le même que dans la bulle N-1, puisqu'après chaque itération on laisse un élément placé à sa place et celui que l'on peut ignorer dans les tours suivants.

Cependant, nous modifions légèrement la fonction de tri pour nous épargner les étapes lorsque nous constatons qu'un élément est déjà ordonné :

fonction tri (monTableau, valeur1, valeur2) {if (valeur1 == valeur2) {return monTableau; } var temp = monTableau [valeur1]; monTableau [valeur1] = monTableau [valeur2]; monTableau [valeur2] = temp; renvoie monTableau ;}

Pour ce faire, nous avons inclus une boucle if dans laquelle elle vérifie si les valeurs correspondent, c'est-à-dire si elles sont déjà commandées.

3. Tri par insertionEnfin nous verrons l'algorithme le plus efficace des trois puisque nous n'aurons pas toujours besoin de N-1 itérations pour placer notre tableau comme nous le verrons ci-dessous.

Cet algorithme d'insertion fonctionne de la même manière que le placement d'une main de cartes dans un jeu de poker lorsque les cartes sont distribuées.
Nous ordonnons généralement les cartes par couleur, et à l'intérieur de celles-ci par ordre croissant comme suit :
D'abord une carte est distribuée, un élément unique qui est ordonné (pour être unique). Puis lorsqu'il y a "j" éléments ordonnés du plus petit au plus grand, on prend l'élément j+1 et on le compare avec tous les éléments qui sont déjà ordonnés. S'il en trouve un plus petit, puisque les plus grands se seront décalés vers la droite, cet élément (j + 1) est inséré, se déplaçant vers le reste.

Le insérer un algorithme traduit en langage JavaScript est comme suit:

fonction insert (myArray) {var tam = myArray.length, temp, place; for (var obj = 0; obj = 0 && monTableau [lieu]> temp; lieu--) {monTableau [lieu + 1] = monTableau [lieu]; } monTableau [lieu + 1] = temp; } renvoie monTableau;}