Le tri à bulles expliqué simplement
Un tutoriel complet pour comprendre le tri à bulles, suivre chaque échange pas à pas et voir comment transformer une liste désordonnée en liste triée.
Le tri à bulles
Introduction
Le tri à bulles est l'un des algorithmes de tri les plus simples à comprendre.
Il n'est pas le plus rapide, mais il est très pédagogique.
Son principe est de comparer des éléments voisins et de les échanger s'ils ne sont pas dans le bon ordre.
Ce que vous allez apprendre
À la fin de ce tutoriel, vous saurez :
- comprendre le principe du tri à bulles ;
- suivre les échanges étape par étape ;
- écrire l'algorithme en JavaScript ;
- repérer ses limites ;
- comprendre pourquoi il sert surtout à apprendre la logique du tri.
1. Le problème de départ
Imaginons une liste non triée :
const numbers = [5, 2, 9, 1, 5, 6];
Le but est de la remettre dans l'ordre croissant.
2. Le principe du tri à bulles
Le tri à bulles compare deux éléments voisins :
- si l'ordre est correct, on ne fait rien ;
- si l'ordre est incorrect, on les échange.
On répète cela plusieurs fois jusqu'à ce que la liste soit triée.
Image mentale
Les plus grandes valeurs "remontent" progressivement vers la fin de la liste, comme des bulles dans l'eau. C'est pour cela que l'algorithme porte ce nom.
3. Exemple pas à pas
Avec la liste :
[5, 2, 9, 1]
Premier passage
- comparer 5 et 2 → échange
- comparer 5 et 9 → rien
- comparer 9 et 1 → échange
Résultat :
[2, 5, 1, 9]
Deuxième passage
- comparer 2 et 5 → rien
- comparer 5 et 1 → échange
- comparer 5 et 9 → rien
Résultat :
[2, 1, 5, 9]
Troisième passage
- comparer 2 et 1 → échange
- comparer 2 et 5 → rien
- comparer 5 et 9 → rien
Résultat final :
[1, 2, 5, 9]
4. Version JavaScript
function bubbleSort(array) {
const result = [...array];
for (let i = 0; i < result.length; i++) {
for (let j = 0; j < result.length - 1 - i; j++) {
if (result[j] > result[j + 1]) {
const temp = result[j];
result[j] = result[j + 1];
result[j + 1] = temp;
}
}
}
return result;
}
Ce qu'il faut comprendre
- on copie le tableau d'origine pour ne pas le modifier directement ;
- la première boucle contrôle le nombre de passages ;
- la deuxième boucle compare les éléments voisins ;
- une variable temporaire sert à faire l'échange.
5. Exemple d'utilisation
const numbers = [5, 2, 9, 1, 5, 6];
console.log(bubbleSort(numbers));
// [1, 2, 5, 5, 6, 9]
6. Pourquoi cet algorithme est utile
Le tri à bulles est surtout intéressant pour apprendre :
- les boucles imbriquées ;
- les échanges de valeurs ;
- la logique de tri ;
- la lecture pas à pas d'un algorithme.
En revanche, il est rarement utilisé tel quel dans des projets réels, car il n'est pas très performant sur de grandes listes.
7. Les cas limites
Liste vide
bubbleSort([]);
Résultat : []
Un seul élément
bubbleSort([10]);
Résultat : [10]
Liste déjà triée
bubbleSort([1, 2, 3, 4]);
Résultat : [1, 2, 3, 4]
8. Erreurs fréquentes
Oublier de copier le tableau
Si vous modifiez directement le tableau d'origine, vous pouvez créer des effets de bord inattendus.
Mal placer les bornes
La condition de la boucle interne doit éviter de comparer un élément avec undefined.
Inverser la condition d'échange
L'échange doit se faire uniquement si l'élément de gauche est plus grand que celui de droite.
9. Amélioration simple
On peut arrêter plus tôt si aucun échange n'a eu lieu pendant un passage.
function bubbleSort(array) {
const result = [...array];
for (let i = 0; i < result.length; i++) {
let swapped = false;
for (let j = 0; j < result.length - 1 - i; j++) {
if (result[j] > result[j + 1]) {
const temp = result[j];
result[j] = result[j + 1];
result[j + 1] = temp;
swapped = true;
}
}
if (!swapped) {
break;
}
}
return result;
}
Cette version est plus efficace si la liste est déjà presque triée.
10. Résumé
Le tri à bulles est un excellent algorithme pour apprendre les bases du tri.
À retenir :
- il compare des éléments voisins ;
- il échange quand l'ordre est mauvais ;
- il répète plusieurs passages ;
- il est simple à comprendre mais pas idéal pour les gros volumes.
Exercices
Exercice 1
Implémentez le tri à bulles sur un tableau de nombres.
Exercice 2
Ajoutez un console.log à chaque échange pour suivre l'évolution du tableau.
Exercice 3
Modifiez l'algorithme pour trier dans l'ordre décroissant.
Exercice 4
Ajoutez l'optimisation avec le drapeau swapped.
Corrigés
Correction exercice 1
function bubbleSort(array) {
const result = [...array];
for (let i = 0; i < result.length; i++) {
for (let j = 0; j < result.length - 1 - i; j++) {
if (result[j] > result[j + 1]) {
const temp = result[j];
result[j] = result[j + 1];
result[j + 1] = temp;
}
}
}
return result;
}
Correction exercice 3
Si l'élément de gauche est plus petit que celui de droite, on échange.
Prochaine étape
Après le tri à bulles, le tri par insertion est une excellente suite, car il repose sur une logique plus naturelle et plus proche de la manière dont on trie parfois des cartes à la main.