Implémentez le tri par insertion à l'aide de JavaScript pour trier un tableau de nombres par ordre croissant

L'art du tri des tableaux est crucial dans le monde de la programmation car il permet une organisation et une manipulation efficaces des données. Lorsqu’il s’agit de mettre en œuvre un algorithme de tri fiable, le tri par insertion devient un choix polyvalent et efficace. Dans cet article, nous plongeons dans le monde complexe de JavaScript et explorons le processus de mise en œuvre du tri par insertion pour trier un tableau de nombres par ordre croissant. En comprenant les mécanismes sous-jacents de l'algorithme et en exploitant la puissance de JavaScript, les développeurs peuvent libérer le potentiel de trier et d'organiser efficacement les données numériques, améliorant ainsi les performances et la convivialité des applications.

Énoncé du problème

Le défi actuel consiste à implémenter un algorithme de tri par insertion utilisant JavaScript pour trier un tableau de nombres par ordre croissant. L'objectif principal est de concevoir un programme capable de réorganiser intelligemment les éléments d'un tableau donné, en garantissant que chaque élément suivant est placé dans la bonne position par rapport à l'élément précédent en fonction de sa valeur numérique. Par exemple, disons que nous fournissons un tableau

[9, 2, 7, 4, 1]

Après avoir exécuté l'algorithme de tri par insertion, le résultat attendu sera un tableau suivant l'ordre croissant, tel que

[1, 2, 4, 7, 9]

Méthode

Dans cet article, nous verrons différentes manières de résoudre les problèmes ci-dessus en JavaScript -

• Tri par insertion de base

• Tri par insertion binaire

• Tri par insertion récursive

Méthode 1 : Tri par insertion de base

L'algorithme de tri par insertion de base maintient un sous-tableau trié dans le tableau. En commençant par le deuxième élément, chaque élément est comparé à l'élément précédent du sous-tableau et déplacé vers la droite s'il est plus petit. Ce processus se poursuit jusqu'à ce que la position correcte soit trouvée et que l'élément soit inséré. Ce processus est répété pour tous les éléments, ce qui donne un tableau entièrement trié.

Exemple

La fonction

insertionSort prend un tableau arr en entrée et renvoie un tableau trié à l'aide de l'algorithme de tri par insertion. Il itère à partir du deuxième élément et le stocke dans la variable actuelle. La boucle while compare l'élément actuel à l'élément précédent dans le sous-tableau trié, en déplaçant le plus grand élément vers la droite. La boucle continue jusqu'à ce que le début du tableau soit atteint ou qu'un élément plus petit soit trouvé. L'élément actuel est ensuite inséré dans le sous-tableau trié à la position correcte. Ce processus est répété pour tous les éléments, ce qui donne un tableau trié.

function insertionSort(arr) {
   for (let i = 1; i < arr.length; i++) {
      let current = arr[i];
      let j = i - 1;
      while (j >= 0 && arr[j] > current) {
         arr[j + 1] = arr[j];
         j--;
      }
      arr[j + 1] = current;
   }
   return arr;
}
 
const arr = [9, 2, 7, 4, 1];
console.log(insertionSort(arr));

Sortie

Ce qui suit est la sortie de la console -

[ 1, 2, 4, 7, 9 ]

Méthode 2 : Tri par insertion binaire

L'algorithme de tri par insertion binaire améliore l'efficacité du tri par insertion de base en utilisant une recherche binaire dans le sous-tableau trié pour déterminer la position correcte de chaque élément. Au lieu d'une recherche linéaire, une recherche binaire est effectuée en comparant l'élément actuel à l'élément central du sous-tableau et en ajustant les limites de recherche en conséquence. Une fois le point d'insertion déterminé, l'élément est déplacé vers la droite pour faire de la place et l'élément actuel est inséré. Ce processus est répété pour tous les éléments, ce qui donne un tableau entièrement trié.

Exemple

La fonction

binaryInsertionSort prend le tableau arr et renvoie un tableau trié à l'aide de l'algorithme de tri par insertion binaire. Il itère à partir du deuxième élément, en supposant que le premier élément est trié. L'élément actuel est stocké dans la variable actuelle. L'algorithme effectue une recherche binaire dans un sous-tableau trié pour trouver la position correcte de l'élément actuel en le comparant à l'élément du milieu et en ajustant les limites de recherche. Une fois la position trouvée, l'algorithme déplace l'élément vers la droite et insère l'élément actuel dans la bonne position. Ce processus est répété pour tous les éléments, ce qui donne un tableau trié.

function binaryInsertionSort(arr) {
   for (let i = 1; i < arr.length; i++) {
      let current = arr[i];
      let left = 0;
      let right = i - 1;
      while (left <= right) {
         let mid = Math.floor((left + right) / 2);
         if (current < arr[mid]) {
            right = mid - 1;
         } else {
            left = mid + 1;
         }
      }
      for (let j = i - 1; j >= left; j--) {
         arr[j + 1] = arr[j];
      }
      arr[left] = current;
   }
   return arr;
}
 
const arr = [9, 2, 7, 4, 1];
console.log(binaryInsertionSort(arr));

Sortie

Ce qui suit est la sortie de la console -

[ 1, 2, 4, 7, 9 ]

Méthode 3 : Tri par insertion récursive

L'algorithme de tri par insertion récursive est une version récursive du tri par insertion qui utilise la récursion pour trier les tableaux. Pour les sous-tableaux de taille 1 ou inférieure, il les considère déjà triés. Pour les sous-tableaux plus grands, il s'appelle récursivement pour trier le sous-tableau sans le dernier élément. Une fois l'appel récursif renvoyé et le sous-tableau trié, l'algorithme place le dernier élément à la position correcte dans le sous-tableau trié. Ceci est réalisé en comparant le dernier élément aux éléments du sous-tableau trié et en les décalant vers la droite si nécessaire. Répétez ce processus jusqu'à ce que tous les éléments soient insérés dans les positions correctes, ce qui donne un tableau entièrement trié.

Exemple

La fonction recursiveInsertionSort applique de manière récursive l'algorithme de tri par insertion au tableau d'entrée. Il vérifie si le tableau est trié et le renvoie si c'est le cas. Sinon, il s'appelle récursivement sur un sous-tableau de taille n - 1. Après avoir été appelée de manière récursive, la fonction utilise une boucle while pour comparer le dernier élément aux éléments du sous-tableau trié. Si un élément est plus grand, il sera déplacé vers la droite. Ce processus se poursuit jusqu'à ce que la boucle atteigne le début du tableau ou qu'un élément plus petit soit trouvé. Enfin, le dernier élément est inséré à la bonne position. Ce processus est répété pour tous les éléments, ce qui donne un tableau trié.

function recursiveInsertionSort(arr, n = arr.length) {
   if (n <= 1) return arr;
 
   recursiveInsertionSort(arr, n - 1);
 
   let last = arr[n - 1];
   let j = n - 2;
 
   while (j >= 0 && arr[j] > last) {
      arr[j + 1] = arr[j];
      j--;
   }
 
   arr[j + 1] = last;
 
   return arr;
}
 
const arr = [9, 2, 7, 4, 1];
console.log(recursiveInsertionSort(arr));

Sortie

Ce qui suit est la sortie de la console -

[ 1, 2, 4, 7, 9 ]

结论

最终，使用 JavaScript 实现插入排序算法以升序排列数字数组，对于寻求熟练排序方法的开发人员来说是一个精明的选择。通过迭代地将元素放置在适当的位置，该算法展示了一种组织数值数据的敏锐方法。虽然插入排序可能不像其他排序技术那样广受好评，但它的效率和简单性使其在某些情况下成为非常宝贵的工具。在 JavaScript 中使用此算法使开发人员能够在其编码库中使用鲜为人知但功能强大的工具，从而生成精简且有序的数组。总之，利用 JavaScript 中插入排序算法的强大功能，对于那些在数组排序中寻求精确性和优雅性的人来说，是一种不切实际的努力。

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!