Comprendre et implémenter les algorithmes de tri
Utilisez les flèches, cliquez ou glissez pour naviguer
1. Comprendre pourquoi trier
Cas d'usage réels : classement, recherche, affichage
2. Implémenter le tri à bulles
Comparer les voisins, faire remonter le plus grand
3. Implémenter le tri par sélection
Trouver le minimum, le placer au début
4. Visualiser Ă©tape par Ă©tape
Voir le tableau Ă©voluer Ă chaque passe
Pourquoi trier ?
Cas d'usage réels : classement, recherche binaire, affichage
Tri Ă bulles (bubble sort)
Le plus simple — comparer les voisins, faire remonter le plus grand
Visualisation du tri Ă bulles
Étape par étape avec un petit tableau
Tri par sélection (selection sort)
Trouver le minimum, le placer au début
Comparaison
Les deux sont O(n²) mais selection sort fait moins de swaps
Trier est une opération fondamentale en programmation
Un tableau trié permet des opérations beaucoup plus efficaces
đź“Š
Classement
Top scores, meilleurs ventes, résultats de recherche
🔍
Recherche binaire
Nécessite un tableau trié — O(log n) au lieu de O(n)
📱
Affichage
Liste de contacts par ordre alphabétique
Sans tri, on doit parcourir tout le tableau pour trouver le plus grand/petit
L'algorithme de tri le plus simple et intuitif
Comparer les voisins et les échanger si nécessaire
Les plus grands éléments "remontent" comme des bulles
1
Comparer
Regarder deux éléments côte à côte
2
Échanger
Si le gauche > droit, on les swap
3
Répéter
Jusqu'à ce que tout soit trié
Imaginez des bulles dans l'eau...
Les grosses bulles remontent Ă la surface
Les petites restent en bas
Grosse bulle
Moyenne
Petite
Les plus grands éléments "flottent" vers la fin du tableau
// Tri Ă bulles - Faire remonter les plus grands
FONCTION triABulles(tableau)
POUR i DE 0 À tableau.longueur - 1
POUR j DE 0 À tableau.longueur - 1 - i
SI tableau[j] > tableau[j + 1]
// Échanger les deux éléments
temp = tableau[j]
tableau[j] = tableau[j + 1]
tableau[j + 1] = temp
FIN SI
FIN POUR
FIN POUR
FIN FONCTION
Deux boucles imbriquées = O(n²)
function triABulles(tableau) {
for (let i = 0; i < tableau.length; i++) {
for (let j = 0; j < tableau.length - 1 - i; j++) {
if (tableau[j] > tableau[j + 1]) {
// Swap avec destructuring
[tableau[j], tableau[j + 1]] = [tableau[j + 1], tableau[j]];
}
}
}
return tableau;
}
Le destructuring `[a, b] = [b, a]` Ă©vite la variable temporaire!
Tableau initial : [5, 3, 8, 1, 2]
Comparer 5 et 3 → Échanger
Comparer 5 et 8 → Pas d'échange
Comparer 8 et 1 → Échanger
Comparer 8 et 2 → Échanger
8 a "remonté" à la fin!
Après passe 1 : [3, 5, 1, 2, 8] — 8 est en place!
Comparer 3 et 5 → Pas d'échange
Comparer 5 et 1 → Échanger
Comparer 5 et 2 → Échanger
5 a "remonté" — 8 et 5 sont en place!
Après passe 2 : [3, 1, 2, 5, 8] — 5 et 8 en place!
Comparer 3 et 1 → Échanger
Comparer 3 et 2 → Échanger
3, 5, 8 sont en place!
Passe 4 : Comparer 1 et 2 → Déjà trié!
Tableau trié!
Deux boucles imbriquées = n × n comparaisons
Pour un tableau de 5 éléments : ~25 comparaisons
10 éléments
~100 ops
100 éléments
~10 000 ops
1 000 éléments
~1 000 000 ops
Trouver le minimum et le placer au bon endroit
Plus efficace que le tri Ă bulles en termes d'Ă©changes
1
Trouver le min
Parcourir pour trouver le plus petit
2
Placer au début
L'échanger avec le premier élément
3
Répéter
Sur le reste du tableau
// Tri par sélection - Placer le minimum au début
FONCTION triParSelection(tableau)
POUR i DE 0 À tableau.longueur - 2
minIndex = i
POUR j DE i + 1 À tableau.longueur - 1
SI tableau[j] < tableau[minIndex]
minIndex = j
FIN SI
FIN POUR
// Échanger le minimum avec l'élément à l'index i
SI minIndex ≠i
ÉCHANGER tableau[i] ET tableau[minIndex]
FIN SI
FIN POUR
FIN FONCTION
Un seul swap par passe au lieu de plusieurs!
function triParSelection(tableau) {
for (let i = 0; i < tableau.length - 1; i++) {
let minIndex = i;
for (let j = i + 1; j < tableau.length; j++) {
if (tableau[j] < tableau[minIndex]) {
minIndex = j;
}
}
if (minIndex !== i) {
[tableau[i], tableau[minIndex]] = [tableau[minIndex], tableau[i]];
}
}
return tableau;
}
On ne swap qu'à la fin de chaque passe — plus efficace!
Tableau initial : [5, 3, 8, 1, 2]
Trouver le minimum dans tout le tableau
Minimum = 1 (index 3)
Échanger avec l'index 0
1 est maintenant en place!
Après étape 1 : [1, 3, 8, 5, 2] — 1 est en place!
Trouver le minimum dans [3, 8, 5, 2]
Minimum = 2 (index 4)
Échanger avec l'index 1
1 et 2 sont en place!
Après étape 2 : [1, 2, 8, 5, 3]
Trouver le minimum dans [8, 5, 3]
Minimum = 3 (index 4)
Échanger avec l'index 2
1, 2, 3 sont en place!
Étape 4 : min de [5, 8] = 5 → déjà en place!
Tableau trié!
| Critère | Tri à bulles | Tri par sélection |
|---|---|---|
| Complexité | O(n²) | O(n²) |
| Comparaisons | ~n²/2 | ~n²/2 |
| Échanges (swaps) | Jusqu'à n² | Maximum n-1 |
| Stabilité | Stable | Instable |
| Intuitif | Très intuitif | Moins intuitif |
Selection sort fait moins de swaps — utile si l'échange est coûteux!
Ces deux algorithmes sont peu efficaces pour les grands tableaux
En pratique, on utilise des algorithmes O(n log n) comme quicksort ou mergesort
Visualiser le tableau Ă chaque Ă©tape
La visualisation est essentielle pour comprendre
Tri à bulles : les gros éléments "remontent"
Le plus intuitif, mais beaucoup de swaps
Tri par sélection : trouver le minimum
Moins de swaps, un par passe maximum
Les deux sont O(n²)
Pas efficaces pour les grands tableaux
Boucles imbriquées confuses
Bien séparer :
Le swap nécessite une variable temporaire
Ou utiliser le destructuring :
[a, b] = [b, a]
Confondre index et valeur
tableau[i] est la valeur
i est l'index
Oublier de réduire la boucle
Dans bubble sort, on compare jusqu'Ă
length - 1 - i
car les derniers éléments sont déjà triés
On utilise .sort()
const nombres = [5, 3, 8, 1, 2];
nombres.sort((a, b) => a - b);
// [1, 2, 3, 5, 8]
Mais comprendre ces algorithmes aide Ă penser en algorithmes!
Tri Ă bulles
Tri par sélection
Les deux sont parfaits pour apprendre, mais utilisez .sort() en production!