Le tri par insertion expliqué simplement
Un tutoriel complet pour comprendre le tri par insertion, suivre son fonctionnement et apprendre pourquoi il est souvent plus naturel que le tri à bulles.
Le tri par insertion
Introduction
Le tri par insertion est un algorithme très utile pour comprendre une logique de tri plus naturelle.
L'idée est simple : on construit progressivement une partie triée du tableau, en insérant chaque nouvel élément à sa bonne place.
Ce que vous allez apprendre
À la fin de ce tutoriel, vous saurez :
- comprendre le principe du tri par insertion ;
- suivre l'algorithme pas à pas ;
- l'implémenter en JavaScript ;
- comprendre dans quels cas il est intéressant ;
- voir la différence avec le tri à bulles.
1. Le problème de départ
Prenons une liste de nombres :
const numbers = [7, 4, 5, 2, 9];
Le but est de la trier dans l'ordre croissant.
2. L'idée du tri par insertion
On considère que le premier élément est déjà trié.
Ensuite :
- on prend l'élément suivant ;
- on le compare avec les éléments déjà triés ;
- on le place à la bonne position ;
- on recommence avec l'élément suivant.
C'est une méthode très intuitive.
3. Exemple pas à pas
Avec la liste :
[7, 4, 5, 2]
Départ
On considère que 7 est déjà trié.
Insertion de 4
4 doit aller avant 7.
Résultat :
[4, 7, 5, 2]
Insertion de 5
5 doit se placer entre 4 et 7.
Résultat :
[4, 5, 7, 2]
Insertion de 2
2 doit aller au début.
Résultat final :
[2, 4, 5, 7]
4. Version JavaScript
function insertionSort(array) {
const result = [...array];
for (let i = 1; i < result.length; i++) {
const current = result[i];
let j = i - 1;
while (j >= 0 && result[j] > current) {
result[j + 1] = result[j];
j--;
}
result[j + 1] = current;
}
return result;
}
Explication
currentcontient l'élément à insérer ;jpermet de remonter dans la partie déjà triée ;- tant que l'élément courant est plus petit, on décale les éléments vers la droite ;
- dès que la bonne position est trouvée, on insère l'élément.
5. Exemple d'utilisation
const numbers = [7, 4, 5, 2, 9];
console.log(insertionSort(numbers));
// [2, 4, 5, 7, 9]
6. Pourquoi cet algorithme est intéressant
Le tri par insertion est souvent plus efficace que le tri à bulles sur de petites listes ou sur des listes déjà presque triées.
Il est aussi plus proche de la manière dont un humain trie parfois des cartes dans sa main.
7. Les cas limites
Tableau vide
insertionSort([]);
Résultat : []
Un seul élément
insertionSort([10]);
Résultat : [10]
Liste déjà triée
insertionSort([1, 2, 3, 4]);
Résultat : [1, 2, 3, 4]
8. Différence avec le tri à bulles
Tri à bulles
Il compare des éléments voisins et les échange plusieurs fois.
Tri par insertion
Il construit une partie triée et insère chaque nouvel élément au bon endroit.
Le tri par insertion est souvent plus naturel à comprendre.
9. Erreurs fréquentes
Oublier de copier le tableau
Comme pour les autres algorithmes, évitez de modifier directement la donnée d'origine si vous voulez garder une fonction propre.
Mal gérer j
Le while doit s'arrêter quand j devient négatif.
Oublier la réinsertion
À la fin du décalage, il faut bien replacer current à la bonne position.
10. Résumé
Le tri par insertion est un algorithme simple, efficace sur les petites listes et très utile pour apprendre la logique du tri.
À retenir :
- on construit progressivement une partie triée ;
- on insère chaque élément à sa place ;
- il est souvent plus naturel que le tri à bulles ;
- il est très utile pour comprendre les bases du tri.
Exercices
Exercice 1
Implémentez le tri par insertion en JavaScript.
Exercice 2
Ajoutez des console.log pour afficher l'état du tableau à chaque insertion.
Exercice 3
Modifiez l'algorithme pour trier dans l'ordre décroissant.
Exercice 4
Testez votre fonction avec une liste déjà triée.
Corrigés
Correction exercice 1
function insertionSort(array) {
const result = [...array];
for (let i = 1; i < result.length; i++) {
const current = result[i];
let j = i - 1;
while (j >= 0 && result[j] > current) {
result[j + 1] = result[j];
j--;
}
result[j + 1] = current;
}
return result;
}
Correction exercice 3
while (j >= 0 && result[j] < current) {
}
Prochaine étape
Une fois le tri par insertion compris, vous avez déjà une bonne base pour comprendre des tris plus avancés comme le tri fusion ou le tri rapide.