Trier des données est l'une des opérations fondamentales en informatique. Que ce soit pour ordonner une liste alphabétiquement, ranger des nombres par ordre croissant ou faciliter la recherche dans une base de données, les algorithmes de tri sont essentiels. Cette fiche présente les principaux algorithmes, leurs caractéristiques et leurs performances.
Pourquoi trier des données ? Le tri permet d'optimiser de nombreuses opérations comme la recherche (on passe d'une complexité O(n) à O(log n)), de faciliter l'affichage des données dans une interface, et de préparer les données pour d'autres algorithmes qui nécessitent des entrées triées.
1. Le Tri par Sélection (Selection Sort)
Le tri par sélection est l'un des algorithmes de tri les plus simples conceptuellement. Son principe est de parcourir le tableau, chercher l'élément minimum, puis l'échanger avec l'élément à la première position. On recommence ensuite avec le sous-tableau restant.
Principe de l'algorithme
- Parcourir le tableau pour trouver l'élément minimum
- Échanger cet élément avec celui à la première position
- Répéter avec le sous-tableau excluant la première position
- Continuer jusqu'à ce que tout le tableau soit trié
Exemple d'implémentation en TypeScript
function selectionSort(arr: number[]): number[] {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
// Trouver l'indice du minimum dans le reste du tableau
let minIndex = i;
for (let j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// Si le minimum n'est pas déjà à la bonne place, échanger
if (minIndex !== i) {
// Échange des valeurs
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
}
return arr;
}
// Exemple d'utilisation
const array = [5, 3, 8, 1, 9, 6];
console.log(selectionSort(array)); // [1, 3, 5, 6, 8, 9]
Complexité
- Temporelle : O(n²) dans tous les cas, car l'algorithme effectue toujours n(n-1)/2 comparaisons
- Spatiale : O(1), tri en place qui ne nécessite qu'un espace constant supplémentaire
2. Le Tri par Insertion (Insertion Sort)
Le tri par insertion fonctionne comme on trie naturellement des cartes à jouer : on prend les éléments un par un et on les insère à la bonne position dans la partie déjà triée du tableau.
Principe de l'algorithme
- Commencer avec le deuxième élément (le premier est considéré comme trié)
- Comparer cet élément avec tous les éléments dans la partie triée
- Décaler les éléments plus grands pour faire de la place
- Insérer l'élément à la position correcte
- Répéter pour tous les éléments restants
Exemple d'implémentation en TypeScript
function insertionSort(arr: number[]): number[] {
const n = arr.length;
for (let i = 1; i < n; i++) {
// Sauvegarder la valeur courante à insérer
const current = arr[i];
// Trouver la position d'insertion dans la partie triée
let j = i - 1;
while (j >= 0 && arr[j] > current) {
// Décaler les éléments plus grands
arr[j + 1] = arr[j];
j--;
}
// Insérer l'élément à la bonne position
arr[j + 1] = current;
}
return arr;
}
// Exemple d'utilisation
const array = [5, 3, 8, 1, 9, 6];
console.log(insertionSort(array)); // [1, 3, 5, 6, 8, 9]
Complexité
- Temporelle :
- Pire cas : O(n²) lorsque le tableau est trié en ordre inverse
- Meilleur cas : O(n) lorsque le tableau est déjà trié
- Spatiale : O(1), tri en place avec espace constant
3. Le Tri à Bulles (Bubble Sort)
Le tri à bulles compare les éléments adjacents et les échange s'ils sont dans le mauvais ordre. Les éléments plus grands "remontent" comme des bulles vers la fin du tableau, d'où son nom.
Principe de l'algorithme
- Parcourir le tableau du début à la fin
- Comparer chaque paire d'éléments adjacents
- Si une paire est dans le mauvais ordre, échanger les éléments
- Répéter jusqu'à ce qu'aucun échange ne soit nécessaire
4. Le Tri Rapide (Quicksort)
Le tri rapide (Quicksort) est un algorithme de tri efficient qui utilise la stratégie "diviser pour régner". Il choisit un élément pivot, répartit les autres éléments en deux sous-tableaux (ceux inférieurs et ceux supérieurs au pivot), puis trie récursivement ces sous-tableaux. C'est l'un des algorithmes de tri les plus utilisés dans la pratique en raison de ses excellentes performances dans la plupart des cas.
Principe de l'algorithme
- Choisir un élément pivot (généralement le dernier élément)
- Réorganiser les éléments : les plus petits à gauche du pivot, les plus grands à droite
- Placer le pivot à sa position finale
- Répéter récursivement ce processus pour les sous-tableaux gauche et droit
5. Autres Algorithmes de Tri Importants
Bien que nous ayons détaillé les quatre algorithmes de tri les plus fondamentaux, il existe d'autres méthodes de tri importantes à connaître :
Tri par Fusion (Merge Sort)
Basé également sur "diviser pour régner", il divise le tableau en deux, trie les deux moitiés, puis les fusionne. Sa complexité est de O(n log n) dans tous les cas, mais il nécessite un espace supplémentaire de O(n).
Tri par Tas (Heap Sort)
Utilise une structure de données appelée "tas" (heap) pour maintenir l'ordre des éléments. Complexité temporelle de O(n log n) dans tous les cas et spatiale de O(1).
Tri par Comptage (Counting Sort)
Pour des tableaux avec une plage de valeurs connue et limitée. Complexité temporelle de O(n+k) où k est la plage des valeurs.
Comparaison des Performances
| Algorithme | Meilleur Cas | Cas Moyen | Pire Cas | Espace | Stable |
|---|---|---|---|---|---|
| Sélection | O(n²) | O(n²) | O(n²) | O(1) | Non |
| Insertion | O(n) | O(n²) | O(n²) | O(1) | Oui |
| Bulles | O(n) | O(n²) | O(n²) | O(1) | Oui |
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) | Non |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Oui |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | Non |
Stabilité d'un algorithme de tri : Un algorithme de tri est dit "stable" s'il préserve l'ordre relatif des éléments égaux. Cela est important, par exemple, si vous triez une liste de personnes d'abord par âge, puis par nom - un tri stable garantit que l'ordre des noms pour les personnes du même âge sera préservé.
À Retenir
- Tri par sélection et tri à bulles : Simples à comprendre et à implémenter, mais inefficaces pour les grandes quantités de données (O(n²)).
- Tri par insertion : Excellent pour les petits tableaux ou les tableaux presque triés (O(n) dans le meilleur des cas).
- Quicksort : Très rapide en pratique, souvent utilisé dans les bibliothèques standards (O(n log n) en moyenne).
- Merge sort : Garantit O(n log n) dans tous les cas, mais nécessite un espace supplémentaire.
- Le choix de l'algorithme dépend de la taille des données, de leur ordre initial, et des contraintes d'espace et de stabilité.
- Dans la pratique, de nombreuses implémentations utilisent des algorithmes hybrides, combinant les avantages de différentes méthodes selon la taille et les caractéristiques des données.