Qu'est ce que la methode de tri par insertion ?
Le tri par insertion est une méthode de tri dans laquelle les éléments de la liste sont insérés un par un à leur place appropriée parmi les éléments déjà triés. À chaque itération, un élément non trié est extrait de la liste et inséré à sa bonne position dans la partie triée de la liste. Cette méthode est similaire à la manière dont on trie des cartes à jouer lorsqu'on les insère dans une main déjà triée.
Par exemple voici une video explicative:
Voici ma méthode pour le tri part insertion :
function generationList() {
let list = [];//créer une liste
while (list.length < 10) { //tant que la longueur de la liste est inferieur a 10 alors:
let random_nombre = Math.floor(Math.random() * 100) + 1; // Génère un nombre aléatoire entre 1 et 100
if (!list.includes(random_nombre)) {// Vérifie si le nombre généré n'est pas déjà présent dans la liste
list.push(random_nombre);// Ajoute le nombre généré à la liste s'il n'est pas déjà dans la liste
}
}
return list; // Retourne la liste générée
}
function triInsertion(t) { // Parcourt la liste à partir du deuxième élément
for (let j = 1; j < t.length; j++) {
let i = j - 1;
let k = t[j];
while (i >= 0 && t[i] > k) {// Tant que l'élément à l'indice i est plus grand que k et i est positif
t[i + 1] = t[i];// Décale l'élément à la position i+1 vers la droite
i--;//diminnue la valeur de i
}
t[i + 1] = k;// Met k à la bonne position dans la partie triée de la liste
}
return t;//retourne a la liste triée
}
function consoleAffichage() {
let randomList = generationList(); genère unn liste aléatoire
console.log("avant le tri par insertion:", randomList);// Affiche la liste avant le tri
triInsertion(randomList);// Trie la liste par insertion
console.log("après le tri par insertion:", randomList);// Affiche la liste apres le tri
}
Avant de cliquer sur le bouton faite 'inspecter'puis 'console' et ensuite cliquez sur le bouton 'Démarrer le tri par insertion'
Tout d'abord ce programme permet de générer une liste de chiffre de manière a ce que tous les chiffres sont differents et sont compris entre 1 et 100 ,puis une fois cette liste faite le tri par insertion commence.Pour commencer le programme commence par le second element donc on regarde si il y a un chiffre avant lui qui est plus grand que celui-ci, alors on met le plus petit chiffre devant le plus grand puis on fait coulisser tous les autres chiffres vers la droite pour combler les trous.Par contre si les chiffres d'avant sont plus petit alors on ne change rien.Ensuite on passe au rang suivant donc au troisième élément.On regarde si il y a une chiffre plus grand que lui ou non,si il y a un chiffre plus grand que lui on met le chiffre plus petit devant le chiffre plus grand et on fait coulisser vers la droite ou alors on ne fait rien et on passe a l'element suivant et ainsi de suite le programme s'arretera lorque la liste et rangée du plus petit au plus grand c'est a dire par ordre croisant.
Qu'est ce que la methode de tri par selection ?
Le tri par sélection est un algorithme de tri simple et intuitif. Il fonctionne en sélectionnant répétitivement l'élément le plus petit (ou le plus grand, selon l'ordre souhaité) parmi ceux restants et en le plaçant à la bonne position. Ce processus se répète jusqu'à ce que tous les éléments soient triés. En termes de complexité, le tri par sélection a une complexité quadratique, ce qui signifie qu'il n'est pas très efficace pour de grandes quantités de données, mais il reste utile pour de petites listes ou comme composant dans des algorithmes plus complexes.
Par exemple voici une video explicative:
Voici ma méthode pour le tri par selection:
function generationList() {
// Définit une fonction pour générer une liste de 10 chiffres différents entre 1 et 100
let list = [];
while (list.length < 10) { // Tant que la longueur de la liste est inférieure à 10
let random_nombre = Math.floor(Math.random() * 100) + 1; // Génère un nombre aléatoire entre 1 et 100
if (!list.includes(random_nombre)) { // Vérifie si le nombre généré n'est pas déjà présent dans la liste
list.push(random_nombre); // Ajoute le nombre généré à la liste s'il n'est pas déjà présent
}
}
return list; // Retourne la liste générée
}
function selectionSort(t) {
// Définit une fonction pour trier une liste d'entiers par la méthode de tri par sélection
for (let i = 0; i < t.length - 1; i++) { // Parcourt la liste
let minIndex = i; // Initialise l'indice du minimum à l'indice actuel
for (let j = i + 1; j < t.length; j++) { // Parcourt le reste de la liste
if (t[j] < t[minIndex]) { // Si l'élément à l'indice j est inférieur à l'élément à l'indice minIndex
minIndex = j; // Met à jour l'indice du minimum
}
}
// Échange l'élément à l'indice i avec l'élément à l'indice minIndex
let temp = t[i];
t[i] = t[minIndex];
t[minIndex] = temp;
}
return t; // Retourne le tableau trié
}
function consoleAffichage() {
// Définit une fonction pour afficher dans la console une liste avant et après le tri par sélection
let randomList = generationList(); // Génère une liste aléatoire
console.log("avant le tri par sélection:", randomList); // Affiche la liste avant le tri
selectionSort(randomList); // Trie la liste par sélection
console.log("après le tri par sélection:", randomList); // Affiche la liste après le tri
}
Avant de cliquer sur le bouton faite 'inspecter'puis 'console' et ensuite cliquez sur le bouton 'Démarrer le tri par selection'
Tout d'abord ce programme permet de générer une liste de chiffre de manière a ce que tous les chiffres sont differents et sont compris entre 1 et 100 ,puis une fois cette liste faite le tri par selection commence.Pour commencer le programme commence par le premier element donc on regarde tout les chiffres et ont va repèrer si il ya a un chiffre plus petit que le chiffre du depart parmis tout les autres chiffres.Si cela ce produit alors ces 2 chiffres s'echange leur place mais si il n'y a aucun chiffre plus petit que le chiffre du depart alors on ne fait rien.Ensuite on passe a l'element suivant,donc on regarde si il ya a un chiffre plus petit que ce chiffre si oui alors on les echanges si non alors on ne fait rien.Le programme s'arretera lorsque que la suite sera du plus grand au plus petit.