Le tri par insertion consiste à placer les éléments de la liste du plus petit jusqu'au plus grand à chaque boucle. On compare les éléments de la première paire et on les échange si le premier est plus grand que le deuxième, puis on descend jusqu'à ce que les éléments correspondent.
// Fonction pour trier une liste en utilisant l'algorithme de tri par insertion
function sortInsertion(method) {
// Récupère la liste à trier à partir des variables globales de la fenêtre
let list = window[method + "List"];
// Vérifie si une liste existe
if (!list) {
// Affiche une alerte si aucune liste n'est trouvée
alert("Veuillez d'abord créer une liste aléatoire.");
return; // Sort de la fonction
}
// Appelle la fonction insertSort pour trier la liste
let steps = insertSort(list.slice());
// Affiche la liste triée dans la console
console.log("Liste triée :", steps[steps.length - 1]);
// Affiche une alerte pour informer que la liste a été triée avec succès
alert("Liste triée avec succès !");
// Identifiant de l'élément HTML pour afficher les étapes de tri
let stepsId = method + "-steps";
// Récupère l'élément HTML où afficher les étapes de tri
let stepsText = document.getElementById(stepsId);
// Définit le texte pour les étapes de tri
stepsText.innerText = "Étapes de tri :";
// Crée une liste HTML non ordonnée pour afficher les étapes de tri
let ul = document.createElement("ul");
// Parcourt chaque étape de tri et crée un élément de liste pour l'afficher
steps.forEach(function(step, index) {
let li = document.createElement("li");
li.innerText = "Étape " + (index + 1) + " : " + step.join(", ");
ul.appendChild(li);
});
// Ajoute la liste d'étapes de tri à l'élément HTML
stepsText.appendChild(ul);
}
// Fonction pour trier un tableau avec l'algorithme de tri par insertion et enregistrer les étapes
function insertSort(arr) {
// Initialise un tableau pour stocker les étapes de tri
let steps = [arr.slice()];
// Parcourt chaque élément du tableau à partir du deuxième
for (let i = 1; i < arr.length; i++) {
// Stocke la valeur actuelle à insérer
let currentValue = arr[i];
// Initialise l'indice de comparaison
let j = i - 1;
// Déplace les éléments plus grands que la valeur actuelle d'une position vers la droite
while (j >= 0 && arr[j] > currentValue) {
arr[j + 1] = arr[j];
j--;
steps.push(arr.slice()); // Enregistre l'étape de tri
}
// Insère la valeur actuelle à sa position correcte
arr[j + 1] = currentValue;
steps.push(arr.slice()); // Enregistre l'étape de tri
}
// Renvoie toutes les étapes de tri
return steps;
}
Liste générée :
Étapes de tri :
Le tri à bulle consiste à placer un à un les plus grands éléments de la liste pour finir sur les plus petits. À chaque boucle, le programme fait monter dans la liste l'élément le plus grand et recommence pour placer correctement les suivants.
// Fonction pour trier une liste en utilisant l'algorithme de tri à bulles
function sortBubble(method) {
// Récupère la liste à trier à partir des variables globales de la fenêtre
let list = window[method + "List"];
// Vérifie si une liste existe
if (!list) {
// Affiche une alerte si aucune liste n'est trouvée
alert("Veuillez d'abord créer une liste aléatoire.");
return; // Sort de la fonction
}
// Appelle la fonction bubbleSort pour trier la liste
let steps = bubbleSort(list.slice());
// Affiche la liste triée dans la console
console.log("Liste triée :", steps[steps.length - 1]);
// Affiche une alerte pour informer que la liste a été triée avec succès
alert("Liste triée avec succès !");
// Identifiant de l'élément HTML pour afficher les étapes de tri
let stepsId = method + "-steps";
// Récupère l'élément HTML où afficher les étapes de tri
let stepsText = document.getElementById(stepsId);
// Définit le texte pour les étapes de tri
stepsText.innerText = "Étapes de tri :";
// Crée une liste HTML non ordonnée pour afficher les étapes de tri
let ul = document.createElement("ul");
// Parcourt chaque étape de tri et crée un élément de liste pour l'afficher
steps.forEach(function(step, index) {
let li = document.createElement("li");
li.innerText = "Étape " + (index + 1) + " : " + step.join(", ");
ul.appendChild(li);
});
// Ajoute la liste d'étapes de tri à l'élément HTML
stepsText.appendChild(ul);
}
// Fonction pour trier un tableau avec l'algorithme de tri à bulles et enregistrer les étapes
function bubbleSort(arr) {
// Initialise un tableau pour stocker les étapes de tri
let steps = [arr.slice()];
// Longueur du tableau
const n = arr.length;
// Variable pour indiquer si des échanges ont été effectués pendant une itération
let swapped;
// Boucle do-while pour effectuer le tri jusqu'à ce qu'aucun échange ne soit nécessaire
do {
swapped = false;
// Boucle for pour parcourir le tableau et comparer les éléments adjacents
for (let i = 0; i < n - 1; i++) {
// Si deux éléments adjacents ne sont pas dans l'ordre, les échanger
if (arr[i] > arr[i + 1]) {
[arr[i], arr[i + 1]] = [arr[i + 1], arr[i]]; // Échange les éléments
swapped = true; // Marque qu'un échange a été effectué
steps.push(arr.slice()); // Enregistre l'étape de tri
}
}
} while (swapped); // Répète tant qu'au moins un échange a été effectué pendant une itération
// Renvoie toutes les étapes de tri
return steps;
}
Liste générée :
Étapes de tri :