Tri insertion en javascript

Le tri d'insertion est un algorithme de tri simple et stable qui choisit un élément dans une liste non triée et l'inserte dans la liste triée à la position appropriée. Alors que le terme algorithme stable fait référence au scénario où deux éléments équivalents apparaissent de manière identique, alors un algorithme stable maintient les éléments à leurs positions relatives après l'exécution de l'algorithme de tri.

L'algorithme de tri d'insertion est très utile dans les cas où nous avons un plus petit nombre d'éléments dans une liste ou où la majeure partie de la liste est déjà triée et moins d'éléments sont déplacés.

Comment fonctionne le tri de l'insertion

Voyons un exemple pour mieux comprendre la logique derrière le type d'insertion. Supposons que nous ayons un tableau non trié de 6 éléments et que nous devons les trier en utilisant le tri de l'insertion:

Maintenant, pour trier le tableau ci-dessus, nous allons itérer le tableau de l'index 1 à la dernière index. Initialement, nous supposons que le 0ème indice du tableau est trié, par la suite, nous ferons une comparaison de l'élément actuel avec son élément précédent. Si l'élément actuel est inférieur à l'élément précédent, nous échangerons leurs positions.

Premier pas
Dans la première étape, nous comparerons l'index 1 avec l'index 0, la valeur du premier index «47» est supérieure à la valeur de 0ème index, il n'y aura donc pas de changement dans la première étape (les éléments n'échangeraient pas):

Deuxième étape
Maintenant, dans la deuxième étape, nous supposerons que les deux premiers éléments sont triés, donc Cursor sera à l'index 2, et nous comparerons l'index 2 avec ses éléments antérieurs:

Puisque «25» est plus petit que «47», échangez «25» et «47». Ensuite, «25» est également comparé à la valeur du 0ème index. '25' est supérieur à «15» donc il ne serait pas échangé.

Le tableau après la deuxième étape sera mis à jour comme suit:

Troisième étape
Ici, dans la troisième étape, nous considérons que les trois premières valeurs sont triées et le curseur sera au troisième index. Nous allons donc comparer le troisième index avec ses valeurs antérieures:

À l'indice 3, «55» est comparé à chaque élément un par un, mais il est supérieur à tous ses éléments antérieurs, il n'y aura donc aucun changement dans la position des éléments du tableau.

Quatrième étape
Nous sommes maintenant à l'index 4, où nous avons une valeur «20» et nous devons le comparer avec tous les éléments précédents du tableau:

Puisque «20» est inférieur à «25», «47» et «55», il sera donc inséré au premier index, et «25», «47» et «55» sera déplacé vers le côté droit par un index (INDEX I + 1) de leurs index actuels.

Le tableau mis à jour sera:

Cinquième étape
Nous sommes maintenant à l'index 5 où la valeur actuelle est «10», ce qui est le plus petit parmi toutes les valeurs de tableau, donc il sera inséré au 0ème index.

De cette façon, l'ensemble du tableau sera trié en utilisant le tri de l'insertion:

Comme nous en avons fini avec la partie conceptuelle du tri de l'insertion, nous allons maintenant implémenter ce concept en JavaScript.

Implémentation du tri d'insertion en JavaScript

Le code d'implémentation du type d'insertion dans JavaScript est le suivant:

fonction insertion_sort (input_array, array_length)

que je, pivot_value, j;
pour (i = 1; i = 0 && input_array [j]> pivot_value)

input_array [j + 1] = input_array [j];
J = J - 1;

input_array [j + 1] = pivot_value;

return input_array;

Selt Input_Array = [15,47,25,55,20,10];
Laissez array_length = input_array.longueur;
insertion_sort (input_array, array_length);
console.log ("Array trié final:", input_array);

Dans le code ci-dessus, nous avons créé une fonction "tri par insertion”Et l'a passé le tableau d'entrée et la longueur du tableau. Ensuite, nous avons itéré la boucle jusqu'à la longueur du tableau.

À l'intérieur de la boucle, nous avons sélectionné le 'pivot_value = input_array [i]'Comme une valeur de pivot pour faire une comparaison de l'élément actuel avec ses éléments antérieurs et définir "j = i-1”Qui représente le dernier élément de notre tableau trié.

Ici, dans chaque itération, l'élément actuel est affecté à la valeur de pivot et la valeur de pivot sera considérée comme le premier élément du tableau non trié à chaque étape.

Nous utilisons une boucle de temps pour trier les éléments de tableau, ici dans cette boucle, nous comparons l'élément actuel avec ses éléments antérieurs. Si l'élément actuel est inférieur à l'un des éléments précédents, et nous avons trouvé la position appropriée pour insérer cet élément dans le tableau trié, nous insérons cet élément à la position appropriée et déplacez les autres éléments un endroit vers le côté droit. Et le phénomène entier est répété pour chaque étape jusqu'à ce que le tableau soit complètement trié.

Sortir

Enfin, nous appelons le «tri par insertion”Fonction et imprimez le tableau trié sur la console du navigateur en utilisant le«console.enregistrer" méthode. La sortie de l'algorithme de tri d'insertion sera:

Conclusion

Le tri de l'insertion est un algorithme de tri qui trie un élément à la fois. Il insère l'élément à la position appropriée un par un pour créer un tableau trié. Il fournit des résultats efficaces si le nombre d'éléments de tableau est petit et que la plupart des éléments de tableau sont déjà triés.

Dans cet article, nous avons envisagé un exemple pour déterminer la logique du tri de l'insertion, nous avons discuté du fonctionnement de l'algorithme de tri d'insertion par rapport à chaque étape et présenté le tableau mis à jour après chaque étape. Et enfin, une fois que nous avons perçu l'idée derrière le tri d'insertion, nous l'avons implémentée en JavaScript.