Implémentation du tri par bac en JavaScript

JavaScriptJavaScriptBeginner
Pratiquer maintenant

This tutorial is from open-source community. Access the source code

💡 Ce tutoriel est traduit par l'IA à partir de la version anglaise. Pour voir la version originale, vous pouvez cliquer ici

Introduction

Dans ce laboratoire, nous allons explorer l'algorithme de tri par bac (bucket sort) en JavaScript. Le tri par bac est un algorithme de tri qui fonctionne en distribuant les éléments d'un tableau dans un certain nombre de bac. Chaque bac est ensuite trié individuellement, soit en utilisant un autre algorithme de tri, soit en appliquant récursivement l'algorithme de tri par bac. Ce laboratoire vous donnera l'occasion de mettre en œuvre cet algorithme et de mieux comprendre comment il fonctionne.


Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL javascript(("JavaScript")) -.-> javascript/BasicConceptsGroup(["Basic Concepts"]) javascript(("JavaScript")) -.-> javascript/AdvancedConceptsGroup(["Advanced Concepts"]) javascript/BasicConceptsGroup -.-> javascript/variables("Variables") javascript/BasicConceptsGroup -.-> javascript/data_types("Data Types") javascript/BasicConceptsGroup -.-> javascript/arith_ops("Arithmetic Operators") javascript/BasicConceptsGroup -.-> javascript/comp_ops("Comparison Operators") javascript/AdvancedConceptsGroup -.-> javascript/higher_funcs("Higher-Order Functions") javascript/AdvancedConceptsGroup -.-> javascript/spread_rest("Spread and Rest Operators") subgraph Lab Skills javascript/variables -.-> lab-28181{{"Implémentation du tri par bac en JavaScript"}} javascript/data_types -.-> lab-28181{{"Implémentation du tri par bac en JavaScript"}} javascript/arith_ops -.-> lab-28181{{"Implémentation du tri par bac en JavaScript"}} javascript/comp_ops -.-> lab-28181{{"Implémentation du tri par bac en JavaScript"}} javascript/higher_funcs -.-> lab-28181{{"Implémentation du tri par bac en JavaScript"}} javascript/spread_rest -.-> lab-28181{{"Implémentation du tri par bac en JavaScript"}} end

Algorithme de tri par bac

Pour utiliser l'algorithme de tri par bac et trier un tableau de nombres, suivez ces étapes :

  1. Ouvrez le Terminal/SSH et tapez node pour commencer à pratiquer la programmation.
  2. Trouvez les valeurs minimale et maximale du tableau donné en utilisant Math.min(), Math.max() et l'opérateur de propagation (...).
  3. Créez le nombre approprié de bac (tableaux vides) en utilisant Array.from() et Math.floor().
  4. Remplissez chaque bac avec les éléments appropriés du tableau en utilisant Array.prototype.forEach().
  5. Triez chaque bac et ajoutez-le au résultat en utilisant Array.prototype.reduce(), l'opérateur de propagation (...) et Array.prototype.sort().

Voici une implémentation exemple de l'algorithme de tri par bac en JavaScript :

const bucketSort = (arr, size = 5) => {
  const min = Math.min(...arr);
  const max = Math.max(...arr);
  const buckets = Array.from(
    { length: Math.floor((max - min) / size) + 1 },
    () => []
  );
  arr.forEach((val) => {
    buckets[Math.floor((val - min) / size)].push(val);
  });
  return buckets.reduce((acc, b) => [...acc, ...b.sort((a, b) => a - b)], []);
};

Pour tester l'algorithme, exécutez le code suivant :

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

Sommaire

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