Introduction aux algorithmes de tri en JavaScript

Semblable à la plupart des autres langages de programmation, vous pouvez exécuter des scénarios dans lesquels vous devez trier certains nombres en JavaScript dans l'ordre croissant ou décroissant. Pour ce faire, nous pouvons utiliser de nombreux algorithmes tels que le tri par bulles, le tri par sélection, le tri par fusion, le tri rapide, etc. Ces algorithmes diffèrent non seulement par leur fonctionnement, mais chacun a également ses différentes exigences en termes de mémoire et de temps, prenons approfondissez certains des algorithmes de tri importants et voyez comment vous pouvez les utiliser dans votre code JavaScript.

Top 6 des algorithmes de tri en JavaScript

Voici quelques algorithmes de tri en javascript expliqués ci-dessous avec des exemples:

1. Algorithme de tri des bulles

Considéré comme l'un des outils les plus courants de ce métier, le tri par bulles fonctionne en créant une boucle qui compare chaque élément du tableau avec un autre élément. Si l'article comparé est plus petit que celui en main, nous échangeons leurs places. Cela continue jusqu'à ce que nous ayons un laissez-passer où aucun élément du tableau n'est plus grand que l'élément qui est à côté.

Bubble Sort a une complexité temporelle O (n 2 ) et une complexité spatiale O (n).

Code:

function swap(arr, firstIndex, secondIndex)(
var temp = arr(firstIndex);
arr(firstIndex) = arr(secondIndex);
arr(secondIndex) = temp;
)
function bubbleSortAlgo(arraaytest)(
var len = arraaytest.length,
i, j, stop;
for (i=0; i < len; i++)(
for (j=0, stop=len-i; j < stop; j++)(
if (arraaytest(j) > arraaytest(j+1))(
swap(arraaytest, j, j+1);
)
)
)return arraaytest;
)
console.log(bubbleSortAlgo((3, 6, 2, 5, -75, 4, 1)));

Production:

2. Algorithme de tri de sélection

Maintenant que nous avons fini de discuter de l'algorithme de tri à bulles, jetons un coup d'œil à un algorithme de tri populaire appelé Tri de sélection.

Contrairement à Bubble Sort, nous nous concentrons sur la recherche de la plus petite valeur dans le tableau pour effectuer le tri. Voici une description détaillée du fonctionnement du tri par sélection:

  • Nous supposons que le premier élément du tableau est le plus petit.
  • Nous comparons cet élément à l'élément suivant du tableau.
  • Si l'élément suivant est plus petit que celui à portée de main, nous définissons l'élément suivant comme la nouvelle valeur la plus petite.
  • Nous continuons à répéter ces étapes jusqu'à ce que nous atteignions la fin du tableau.
  • Lorsque nous trouvons une valeur dans le tableau plus petite que celle avec laquelle nous avons commencé, nous échangeons leurs positions.
  • Nous continuons à faire les comparaisons et à passer au point suivant. Jusqu'à ce que l'ensemble du tableau soit trié.

Tout comme l'algorithme Bubble Sort, le tri Selection a une complexité temporelle O (n 2 ) et une complexité spatiale O (n).

Code:

function SelectionSortAlgo(array, compare_Function) (
function comp(a, b) (
return a - b;
)
var min = 0;
var index = 0;
var temp = 0;
compare_Function = compare_Function || compare;
for (var i = 0; i < array.length; i += 1) (
index = i;
min = array(i);
for (var j = i + 1; j < array.length; j += 1) (
if (compare_Function(min, array(j)) > 0) (
min = array(j);
index = j;
)
)
temp = array(i);
array(i) = min;
array(index) = temp;
)
return array;
)
console.log(SelectionSortAlgo((9, 15, 2, 44, -1, 36, 1), function(a, b) ( return a - b; )));

Production:

3. Algorithme de tri par fusion

Semblable au tri à bulles et au tri par sélection, le tri par fusion est l'un des algorithmes de tri les plus populaires en informatique, vous pouvez l'implémenter dans la plupart des langages de programmation et il a de bonnes performances sans être trop nécessiteux en ressources.

Merge Sort utilise la méthode Divide and conquer pour trier un tableau ou toute liste d'éléments. Le terme divise et conquiert signifie que nous divisons un gros problème en plusieurs petits problèmes, puis nous résolvons ces petits problèmes. Une fois les petits problèmes résolus, nous combinons les résultats qui donnent la solution au gros problème.

Comprendre l'algorithme est simple en fait:

  • Nous divisons le tableau donné en n tableaux chacun de ces tableaux contient seulement 1 élément.
  • Fusionnez les tableaux pour produire un nouveau tableau.
  • Répétez l'étape 2 jusqu'à ce qu'il ne reste qu'un seul tableau, qui sera le tableau trié.

Code:

function merge_sort_algo(left, right)
(
var i = 0;
var j = 0;
var result = ();
while (i < left.length || j < right.length) (
if (i === left.length) (
// j is the only index left_part
result.push(right(j));
j++;
)
else if (j === right.length || left(i) <= right(j)) (
result.push(left(i));
i++;
) else (
result.push(right(j));
j++;
)
)
return result;
)
console.log(merge_sort_algo((1, 44, 6), (84, 7, 5)));

Production:

4. Algorithme de tri rapide

Quicksort est l'un des moyens les plus efficaces de trier les éléments dans les systèmes informatiques. Similaire au tri par fusion, Quicksort fonctionne sur l'algorithme de division et de conquête. Dans ce document, nous trouvons un élément pivot dans le tableau pour comparer tous les autres tableaux d'éléments, puis nous déplaçons les éléments d'une manière où tous les éléments avant nos éléments pivot sélectionnés sont plus petits et tous les éléments après l'élément pivot sont plus grands. Une fois que nous avons fait cela, la clé est de continuer à le faire à plusieurs reprises et nous aurons notre tableau trié.

Voici les étapes à suivre pour implémenter l'algorithme de tri rapide:

  • Nous sélectionnons un élément du tableau et l'appelons «Pivot Point»
  • Nous commençons un pointeur appelé le pointeur gauche à partir duquel se trouve le premier élément du tableau.
  • De même, nous commençons un pointeur appelé le pointeur droit sur le dernier élément du tableau.
  • Si la valeur de l'élément au pointeur gauche est inférieure par rapport au point de pivotement sélectionné, nous déplaçons le pointeur gauche vers la gauche (ajoutez +1 à celui-ci) et continuons à le répéter jusqu'à ce que la valeur au pointeur gauche soit plus grande que la valeur du point de pivot ou égale à celle-ci.
  • Si la valeur de l'élément au pointeur droit de la liste est supérieure à la valeur de l'élément pivot, nous modifions le pointeur droit à gauche. Répétez cette opération jusqu'à ce que la valeur du pointeur de droite soit inférieure (ou égale) à la valeur de pivot.
  • Lorsque la valeur du pointeur gauche est inférieure ou égale à la valeur du pointeur droit, échangez les valeurs.
  • Déplacez le pointeur droit vers la gauche d'un point, le pointeur gauche vers la droite d'un point.
  • Répétez jusqu'à ce que les pointeurs gauche et droit se rencontrent.

Code:

function quickSortAlgo(origArray) (
if (origArray.length <= 1) (
return origArray;
) else (
var left = ();
var right = ();
var newArray = ();
var pivot = origArray.pop();
var length = origArray.length;
for (var i = 0; i < length; i++) (
if (origArray(i) <= pivot) (
left.push(origArray(i));
) else (
right.push(origArray(i));
)
)
return newArray.concat(quickSortAlgo(left), pivot, quickSortAlgo(right));
)
)
var myArray = (13, 50, 2, 45, -1, 74, 11 );
var arreySorted = quickSortAlgo(myArray);
console.log(arreySorted);

Production:

5. Algorithme de tri par insertion

Lorsqu'il s'agit de faciliter la mise en œuvre, le tri par insertion est largement connu comme l'un des algorithmes les plus simples. Dans le tri par insertion, les éléments du tableau sont comparés les uns aux autres, puis disposés dans un ordre particulier. Ceci est très similaire à l'organisation des cartes dans un jeu. Le tri par insertion de nom provient du processus de sélection d'un élément et de l'insertion à sa place correcte, puis de le répéter pour tous les éléments.

Voici comment fonctionne l'algorithme:

  • Le premier élément du tableau est considéré comme déjà trié.
  • Choisissez l'élément suivant du tableau.
  • Comparez l'élément sélectionné avec tous les éléments du tableau.
  • Décale chaque élément du tableau qui est supérieur à la valeur de l'élément sélectionné.
  • Insérez l'élément
  • Répétez les étapes 2 à 5 jusqu'à ce que le tableau soit trié.

Code:

function insertion_Sort_algo(arr)
(
for (var i = 1; i < arr.length; i++)
(
if (arr(i) < arr(0))
(
arr.unshift(arr.splice(i, 1)(0));
)
else if (arr(i) > arr(i-1))
(
continue;
)
else (
for (var j = 1; j < i; j++) (
if (arr(i) > arr(j-1) && arr(i) < arr(j))
(
arr.splice(j, 0, arr.splice(i, 1)(0));
)
)
)
)
return arr;
)
console.log(insertion_Sort_algo((44, 20, 26, 54, -9, 41, 16)));

Production:

6. Algorithme de tri de tas

Le tri en tas est un moyen de trier les éléments en utilisant la structure de données «tas». La méthode est assez similaire à la technique de tri par sélection dont nous avons discuté précédemment. Maintenant, vous vous demandez peut-être à propos des tas et comment sont-ils définis, avant de passer à l'algorithme, comprenons d'abord les tas.

En un mot, un tas est un arbre binaire avec des règles supplémentaires. Une règle stipule que dans le tas, l'arbre doit être un arbre binaire complet, ce qui signifie simplement qu'il est nécessaire de remplir tous les nœuds au niveau actuel avant d'en ajouter un autre. La règle suivante pour le tas est qu'il doit y avoir une relation enfant et parent définie avec les valeurs des éléments du tas.

Dans un tas min, la valeur d'un parent doit être inférieure à ses enfants. Dans un tas max, comme vous pouvez le deviner, la valeur d'un parent doit être supérieure à son enfant.

Maintenant que les définitions sont à l'écart, regardons comment fonctionne le heapsort:

  • Nous construisons d'abord un tas max qui s'assure que l'élément de valeur la plus élevée est au sommet.
  • Nous basculons l'élément supérieur avec le dernier élément du tas et supprimons l'élément supérieur du tas et le stockons sur un tableau trié.
  • Nous continuons à répéter les étapes un et deux jusqu'à ce qu'il ne reste qu'un élément dans le tas.

Une chose à garder à l'esprit est que les tas ne sont pas pris en charge nativement en JavaScript, nous devons donc recourir à l'implémentation de tas en utilisant des tableaux. La complexité spatiale du tri en tas est O (1), ce qui est excellent et bien qu'il soit un peu plus compliqué par rapport au tri par fusion ou au tri par insertion en ce qui concerne la compréhension et la mise en œuvre, je pense que pour des avantages en termes de performances, il est finalement préférable de l'utiliser dans grands projets.

Code:

var arrLength;
function heapRoot(input, i) (
var left = 2 * i + 1;
var right = 2 * i + 2;
var max = i;
if (left input(max)) (
max = left;
)
if (right input(max)) (
max = right;
)
if (max != i) (
swap(input, i, max);
heapRoot(input, max);
)
)
function swap(input, index_A, index_B) (
var temp = input(index_A);
input(index_A) = input(index_B);
input(index_B) = temp;
)
function heapSortAlgo(input) (
arrLength = input.length;
for (var i = Math.floor(arrLength / 2); i >= 0; i -= 1) (
heapRoot(input, i);
)
for (i = input.length - 1; i > 0; i--) (
swap(input, 0, i);
arrLength--;
heapRoot(input, 0);
)
)
var arr = (12, 10, 22, 55, -8, 64, 14);
heapSortAlgo(arr);
console.log(arr);

Production:

Conclusion

Le tri est un élément important de la création d'applications et de sites Web avec JavaScript. Maintenant que vous connaissez certains des algorithmes les plus importants pour faire le travail, vous devriez avoir plus confiance en JS Development.

Un fait important à garder à l'esprit à propos des différents types de tri est que vous n'avez pas vraiment à vous soucier trop de l'algorithme à utiliser dans la plupart des cas. Maintenant que le matériel informatique est si puissant, les processeurs de téléphone et de bureau modernes ne casseront pas de sueur en triant même des centaines d'éléments en quelques millisecondes. Ce n'est que dans les cas où vous êtes coincé avec du matériel lent ou dans des situations où vous pouvez optimiser chaque section de code que la modification des algorithmes de tri peut être bénéfique.

Articles recommandés

Ceci est un guide de tri des algorithmes en JavaScript. Ici, nous discutons des 6 meilleurs algorithmes de tri en javascript ainsi que des exemples et la mise en œuvre du code. Vous pouvez également consulter les articles suivants pour en savoir plus -

  1. Compilateurs JavaScript
  2. Inverser en JavaScript
  3. Introduction à JavaScript
  4. Carrés en Java
  5. Algorithmes de tri rapide en Java
  6. Tableaux dans la structure de données
  7. Algorithme C ++ | Exemples d'algorithme C ++

Catégorie:

Développement de logiciels