Implémentation du tri par insertion en JavaScript

Introduction

Dans ce laboratoire, nous allons explorer la mise en œuvre de l'algorithme de tri par insertion en JavaScript. Nous allons apprendre à trier un tableau de nombres à l'aide de cet algorithme et comprendre la logique derrière. À la fin de ce laboratoire, vous serez capable d'utiliser l'algorithme de tri par insertion pour trier efficacement les tableaux dans vos projets JavaScript.

Tri par insertion en JavaScript

Pour pratiquer la programmation, ouvrez le Terminal/SSH et tapez node. Cet algorithme trie un tableau de nombres en utilisant la méthode de tri par insertion. Suivez ces étapes pour implémenter cet algorithme :

1. Utilisez Array.prototype.reduce() pour itérer sur tous les éléments du tableau donné.
2. Si la length de l'accumulateur est 0, ajoutez l'élément actuel à celui-ci.
3. Utilisez Array.prototype.some() pour itérer sur les résultats dans l'accumulateur jusqu'à trouver la position correcte.
4. Utilisez Array.prototype.splice() pour insérer l'élément actuel dans l'accumulateur.

Voici le code pour implémenter le tri par insertion en JavaScript :

const insertionSort = (arr) =>
  arr.reduce((acc, x) => {
    if (!acc.length) return [x];
    acc.some((y, j) => {
      if (x <= y) {
        acc.splice(j, 0, x);
        return true;
      }
      if (x > y && j === acc.length - 1) {
        acc.splice(j + 1, 0, x);
        return true;
      }
      return false;
    });
    return acc;
  }, []);

Vous pouvez tester l'algorithme avec le code suivant :

insertionSort([6, 3, 4, 1]); // [1, 3, 4, 6]

Sommaire

Félicitations ! Vous avez terminé le laboratoire sur le tri par insertion. Vous pouvez pratiquer d'autres laboratoires sur LabEx pour améliorer vos compétences.