Le tri rapide expliqué simplement
Un tutoriel complet pour comprendre le tri rapide, découvrir le rôle du pivot et voir comment fonctionne le partitionnement en JavaScript.
Le tri rapide
Introduction
Le tri rapide est l'un des algorithmes de tri les plus connus.
Il est souvent très performant en pratique, même si son fonctionnement demande un peu plus d'attention au début.
Son idée principale repose sur un pivot : on choisit une valeur, on sépare les éléments plus petits et plus grands, puis on recommence sur chaque partie.
Ce que vous allez apprendre
À la fin de ce tutoriel, vous saurez :
- comprendre le principe du tri rapide ;
- savoir ce qu'est un pivot ;
- comprendre le partitionnement ;
- écrire une version simple en JavaScript ;
- voir les limites de l'algorithme ;
- le comparer au tri fusion.
1. Le problème de départ
Prenons cette liste :
const numbers = [7, 2, 1, 6, 8, 5, 3, 4];
Le but est de la trier dans l'ordre croissant.
2. L'idée du tri rapide
Le tri rapide fonctionne ainsi :
- choisir un pivot ;
- placer les nombres plus petits à gauche ;
- placer les nombres plus grands à droite ;
- recommencer sur chaque sous-liste.
3. Exemple intuitif
Si le pivot est 5, on peut séparer la liste en deux groupes :
- à gauche : les nombres plus petits que
5; - à droite : les nombres plus grands que
5.
Ensuite, on trie chaque partie de la même manière.
4. Version JavaScript simple
Voici une version lisible et pédagogique :
function quickSort(array) {
if (array.length <= 1) {
return array;
}
const pivot = array[Math.floor(array.length / 2)];
const left = [];
const middle = [];
const right = [];
for (const value of array) {
if (value < pivot) {
left.push(value);
} else if (value > pivot) {
right.push(value);
} else {
middle.push(value);
}
}
return [...quickSort(left), ...middle, ...quickSort(right)];
}
Explication
pivotest la valeur de référence ;leftcontient les valeurs plus petites ;middlecontient les valeurs égales au pivot ;rightcontient les valeurs plus grandes ;- on trie ensuite
leftetrightrécursivement.
5. Exemple d'utilisation
const numbers = [7, 2, 1, 6, 8, 5, 3, 4];
console.log(quickSort(numbers));
// [1, 2, 3, 4, 5, 6, 7, 8]
6. Pourquoi cet algorithme est intéressant
Le tri rapide est souvent très efficace en pratique.
Il est apprécié parce qu'il trie rapidement de grandes listes dans beaucoup de situations réelles.
7. Le rôle du pivot
Le pivot est le point central de l'algorithme.
Un bon choix de pivot peut améliorer le comportement du tri.
Si le pivot est mal choisi de manière répétée, l'algorithme peut devenir moins performant.
8. La récursion
Comme le tri fusion, le tri rapide utilise la récursion.
On trie une sous-liste, puis une autre, jusqu'à arriver à des listes très petites.
Cas de base
if (array.length <= 1) {
return array;
}
9. Les cas limites
Tableau vide
quickSort([]);
Résultat : []
Un seul élément
quickSort([10]);
Résultat : [10]
Liste déjà triée
quickSort([1, 2, 3, 4]);
Résultat : [1, 2, 3, 4]
10. Tri rapide ou tri fusion ?
Tri rapide
- souvent très performant en pratique ;
- repose sur le pivot et le partitionnement ;
- peut être sensible au choix du pivot.
Tri fusion
- très régulier ;
- repose sur la division en deux parties égales ;
- utilise une étape de fusion très claire.
Les deux sont importants à connaître.
11. Erreurs fréquentes
Oublier le cas de base
La récursion doit toujours avoir une condition d'arrêt.
Mal gérer le pivot
Il faut bien séparer les valeurs plus petites, égales et plus grandes.
Modifier la même liste partout
Pour apprendre plus facilement, il est souvent plus clair de retourner une nouvelle liste.
12. Résumé
Le tri rapide est un algorithme puissant qui repose sur le pivot et le partitionnement.
À retenir :
- on choisit un pivot ;
- on sépare les valeurs en plusieurs groupes ;
- on trie récursivement les sous-listes ;
- il est souvent très efficace en pratique.
Exercices
Exercice 1
Implémentez le tri rapide en JavaScript.
Exercice 2
Testez votre fonction avec une liste vide.
Exercice 3
Testez votre fonction avec une liste déjà triée.
Exercice 4
Essayez de modifier le pivot pour prendre le premier élément.
Corrigés
Correction exercice 1
function quickSort(array) {
if (array.length <= 1) {
return array;
}
const pivot = array[Math.floor(array.length / 2)];
const left = [];
const middle = [];
const right = [];
for (const value of array) {
if (value < pivot) {
left.push(value);
} else if (value > pivot) {
right.push(value);
} else {
middle.push(value);
}
}
return [...quickSort(left), ...middle, ...quickSort(right)];
}
Prochaine étape
Une fois le tri rapide compris, vous avez déjà une bonne base pour lire et écrire la plupart des algorithmes de tri classiques.