Le tri fusion expliqué simplement
Un tutoriel complet pour comprendre le tri fusion, découvrir la logique du divide and conquer et l'implémenter pas à pas en JavaScript.
Le tri fusion
Introduction
Le tri fusion est un algorithme de tri plus avancé que le tri à bulles ou le tri par insertion.
Il repose sur une idée très puissante : diviser une liste en deux parties, trier chaque partie séparément, puis les fusionner.
Cette stratégie s'appelle le divide and conquer.
Ce que vous allez apprendre
À la fin de ce tutoriel, vous saurez :
- comprendre le principe du tri fusion ;
- voir pourquoi il est plus performant que les tris simples ;
- écrire l'algorithme en JavaScript ;
- comprendre la notion de récursion ;
- suivre l'étape de fusion pas à pas.
1. Le problème de départ
Prenons cette liste :
const numbers = [8, 4, 2, 9, 5, 1, 6, 3];
Le but est de la trier dans l'ordre croissant.
2. L'idée du tri fusion
Le tri fusion fonctionne en trois temps :
- découper la liste en deux ;
- trier récursivement chaque moitié ;
- fusionner les deux moitiés triées.
3. Exemple visuel
Découpage
On peut voir la liste comme deux moitiés : [8, 4, 2, 9] et [5, 1, 6, 3].
Nouveau découpage
On découpe encore : [8, 4], [2, 9], [5, 1], [6, 3].
Puis encore
On continue jusqu'à obtenir des listes d'un seul élément : [8], [4], [2], [9], [5], [1], [6], [3].
Chaque petit tableau est déjà trié par définition, car il ne contient qu'un seul élément.
4. La fusion
La fusion consiste à prendre deux tableaux triés et à les réunir dans le bon ordre.
Exemple :
Par exemple : [2, 8] et [4, 9].
Résultat :
Le résultat fusionné est : [2, 4, 8, 9].
5. Version JavaScript
function merge(left, right) {
const result = [];
let i = 0;
let j = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
result.push(left[i]);
i++;
} else {
result.push(right[j]);
j++;
}
}
return result.concat(left.slice(i)).concat(right.slice(j));
}
function mergeSort(array) {
if (array.length <= 1) {
return array;
}
const middle = Math.floor(array.length / 2);
const left = array.slice(0, middle);
const right = array.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
Explication
mergeSortcoupe la liste en deux jusqu'à obtenir des sous-listes d'un élément ;mergecompare ensuite les deux listes triées ;- le résultat final est une nouvelle liste triée.
6. Exemple d'utilisation
const numbers = [8, 4, 2, 9, 5, 1, 6, 3];
console.log(mergeSort(numbers));
// [1, 2, 3, 4, 5, 6, 8, 9]
7. Pourquoi le tri fusion est intéressant
Le tri fusion est plus performant que les tris simples sur de grandes listes.
Il est aussi très régulier : même si les données sont déjà presque triées, il garde une bonne stabilité de fonctionnement.
8. Le rôle de la récursion
La récursion consiste à appeler une fonction elle-même.
Dans le tri fusion, cela permet de continuer à découper la liste jusqu'au cas le plus simple : une liste d'un seul élément.
Cas de base
if (array.length <= 1) {
return array;
}
Ce cas de base est indispensable pour éviter une boucle infinie.
9. Les cas limites
Tableau vide
mergeSort([]);
Résultat : []
Un seul élément
mergeSort([10]);
Résultat : [10]
Tableau déjà trié
mergeSort([1, 2, 3, 4]);
Résultat : [1, 2, 3, 4]
10. Erreurs fréquentes
Oublier le cas de base
Sans condition d'arrêt, la récursion ne s'arrête jamais.
Mélanger fusion et découpage
Le découpage et la fusion sont deux étapes différentes.
Modifier le tableau d'origine sans le vouloir
Il est préférable de retourner une nouvelle liste pour garder la fonction plus propre.
11. Résumé
Le tri fusion est un algorithme puissant et élégant.
À retenir :
- il divise la liste en deux ;
- il trie récursivement chaque partie ;
- il fusionne les résultats ;
- il est plus performant que les tris simples sur les grandes listes.
Exercices
Exercice 1
Implémentez le tri fusion en JavaScript.
Exercice 2
Testez la fonction avec une liste vide.
Exercice 3
Testez la fonction avec une liste déjà triée.
Exercice 4
Essayez d'expliquer la fonction merge avec vos propres mots.
Corrigés
Correction exercice 1
function merge(left, right) {
const result = [];
let i = 0;
let j = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
result.push(left[i]);
i++;
} else {
result.push(right[j]);
j++;
}
}
return result.concat(left.slice(i)).concat(right.slice(j));
}
function mergeSort(array) {
if (array.length <= 1) {
return array;
}
const middle = Math.floor(array.length / 2);
const left = array.slice(0, middle);
const right = array.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
Prochaine étape
Après le tri fusion, le tri rapide est un excellent algorithme à découvrir, car il utilise lui aussi le principe du découpage, mais d'une manière différente.