Algorithme de Tri

Tri par Insertion

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 :

Tri à Bulle

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 :