Les algorithmes de tri
Il existe une multitude de façons de trier un tableau. Chaque algorithme a ses avantages selon le contexte (taille des données, données déjà partiellement triées, mémoire disponible…).
Tri par sélection
Section intitulée « Tri par sélection »Principe : on cherche le minimum dans le tableau non trié, on le place en première position, puis on recommence sur le reste.
Exemple pas à pas sur [5, 3, 8, 1, 4] :
[5, 3, 8, 1, 4] → min = 1, échange avec 5 → [1, 3, 8, 5, 4][1, 3, 8, 5, 4] → min = 3, déjà en place → [1, 3, 8, 5, 4][1, 3, 8, 5, 4] → min = 4, échange avec 8 → [1, 3, 4, 5, 8][1, 3, 4, 5, 8] → min = 5, déjà en place → [1, 3, 4, 5, 8]Pseudo-code :
PROCÉDURE triSélection(T : tableau, n : entier)VARIABLES i, j, iMin, temp : entierDÉBUT POUR i ← 0 À n - 2 FAIRE iMin ← i POUR j ← i + 1 À n - 1 FAIRE SI T[j] < T[iMin] ALORS iMin ← j FIN_SI FIN_POUR SI iMin <> i ALORS temp ← T[i] T[i] ← T[iMin] T[iMin] ← temp FIN_SI FIN_POURFINTri à bulles
Section intitulée « Tri à bulles »Principe : on compare chaque paire d’éléments adjacents et on les échange s’ils sont dans le mauvais ordre. Les grands éléments “remontent” progressivement comme des bulles.
Exemple pas à pas sur [5, 3, 8, 1, 4] :
Passe 1 : [3, 5, 1, 4, 8] ← 8 remonte en finPasse 2 : [3, 1, 4, 5, 8] ← 5 se placePasse 3 : [1, 3, 4, 5, 8] ← trié ✓Pseudo-code :
PROCÉDURE triBulles(T : tableau, n : entier)VARIABLES i, j, temp : entier échangé : booléenDÉBUT POUR i ← 0 À n - 2 FAIRE échangé ← faux POUR j ← 0 À n - 2 - i FAIRE SI T[j] > T[j + 1] ALORS temp ← T[j] T[j] ← T[j + 1] T[j + 1] ← temp échangé ← vrai FIN_SI FIN_POUR SI échangé == faux ALORS ARRÊTER {tableau déjà trié : optimisation} FIN_SI FIN_POURFINTri par insertion
Section intitulée « Tri par insertion »Principe : on prend chaque élément un par un et on l’insère à sa bonne place dans la partie déjà triée, comme on trie des cartes dans sa main.
Exemple pas à pas sur [5, 3, 8, 1, 4] :
[5 | 3, 8, 1, 4] → insère 3 → [3, 5 | 8, 1, 4][3, 5 | 8, 1, 4] → 8 en place → [3, 5, 8 | 1, 4][3, 5, 8 | 1, 4] → insère 1 → [1, 3, 5, 8 | 4][1, 3, 5, 8 | 4] → insère 4 → [1, 3, 4, 5, 8]Pseudo-code :
PROCÉDURE triInsertion(T : tableau, n : entier)VARIABLES i, j, clé : entierDÉBUT POUR i ← 1 À n - 1 FAIRE clé ← T[i] j ← i - 1 TANT_QUE j >= 0 ET T[j] > clé FAIRE T[j + 1] ← T[j] j ← j - 1 FIN_TANT_QUE T[j + 1] ← clé FIN_POURFINTri rapide (QuickSort)
Section intitulée « Tri rapide (QuickSort) »Principe : algorithme de type diviser pour régner. On choisit un pivot, on place tous les éléments plus petits à sa gauche et les plus grands à sa droite, puis on applique récursivement le même procédé sur chaque sous-tableau.
Pseudo-code :
PROCÉDURE triRapide(T : tableau, gauche : entier, droite : entier)VARIABLES pivot, i, j, temp : entierDÉBUT SI gauche < droite ALORS pivot ← T[(gauche + droite) / 2] i ← gauche j ← droite
TANT_QUE i <= j FAIRE TANT_QUE T[i] < pivot FAIRE i ← i + 1 FIN_TANT_QUE TANT_QUE T[j] > pivot FAIRE j ← j - 1 FIN_TANT_QUE SI i <= j ALORS temp ← T[i] T[i] ← T[j] T[j] ← temp i ← i + 1 j ← j - 1 FIN_SI FIN_TANT_QUE
triRapide(T, gauche, j) triRapide(T, i, droite) FIN_SIFINComparatif
Section intitulée « Comparatif »| Algorithme | Meilleur cas | Cas moyen | Pire cas | Stable | Remarque |
|---|---|---|---|---|---|
| Sélection | O(n²) | O(n²) | O(n²) | Non | Simple, peu efficace |
| Bulles | O(n) | O(n²) | O(n²) | Oui | Efficace si presque trié |
| Insertion | O(n) | O(n²) | O(n²) | Oui | Très bon sur données partiellement triées |
| Rapide (QuickSort) | O(n log n) | O(n log n) | O(n²) | Non | Meilleur choix général en pratique |