Implémentation de l'algorithme de tri par tas en JavaScript

Introduction

Dans ce laboratoire, nous allons explorer la mise en œuvre de l'algorithme de tri par tas (heapsort) en JavaScript. Le tri par tas est un algorithme de tri basé sur des comparaisons qui fonctionne en divisant un tableau en une région triée et une région non triée, puis en réduisant itérativement la région non triée en extrayant l'élément le plus grand et en le déplaçant dans la région triée. Grâce à ce laboratoire, vous comprendrez mieux comment fonctionne l'algorithme de tri par tas et comment l'implémenter en utilisant la récursivité et les fermetures en JavaScript.

Algorithme de tri par tas

Pour pratiquer la programmation, ouvrez le Terminal/SSH et tapez 'node'. L'algorithme suivant trie un tableau de nombres en utilisant l'algorithme de tri par tas. Suivez ces étapes :

• Utilisez la récursivité dans la fonction.
• Utilisez l'opérateur de propagation (...) pour cloner le tableau original, arr.
• Utilisez des fermetures pour déclarer une variable, l, et une fonction heapify.
• Utilisez une boucle for et Math.floor() en combinaison avec heapify pour créer un tas maximal à partir du tableau.
• Utilisez une boucle for pour réduire progressivement la plage considérée, en utilisant heapify et en échangeant les valeurs si nécessaire pour trier le tableau cloné.

const heapsort = (arr) => {
  const a = [...arr];
  let l = a.length;
  const heapify = (a, i) => {
    const left = 2 * i + 1;
    const right = 2 * i + 2;
    let max = i;
    if (left < l && a[left] > a[max]) max = left;
    if (right < l && a[right] > a[max]) max = right;
    if (max !== i) {
      [a[max], a[i]] = [a[i], a[max]];
      heapify(a, max);
    }
  };
  for (let i = Math.floor(l / 2); i >= 0; i -= 1) heapify(a, i);
  for (let i = a.length - 1; i > 0; i--) {
    [a[0], a[i]] = [a[i], a[0]];
    l--;
    heapify(a, 0);
  }
  return a;
};

Par exemple :

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

Sommaire

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