🎯 Objectifs de la lecon
- •Comprendre le principe du tri par insertion et sa complexité en O(n²).
- •Comprendre le principe du tri fusion (diviser pour régner) et sa complexité en O(n log n).
- •Comprendre le principe du tri rapide (quicksort) et sa complexité moyenne en O(n log n).
- •Savoir implémenter ces trois tris en Python.
Trier une liste est une opération fondamentale en informatique. Dans ce cours, tu vas étudier trois algorithmes de tri classiques : le tri par insertion, le tri fusion et le tri rapide (quicksort). Chacun a ses forces et ses faiblesses en termes de rapidité et d'utilisation mémoire.
Tri par insertion
Le tri par insertion est simple à comprendre. On parcourt la liste de gauche à droite. Pour chaque élément, on l'insère à sa bonne place dans la partie déjà triée (à gauche).
Imagine que tu tries des cartes dans ta main. Tu prends une nouvelle carte et tu la glisses à la bonne position parmi celles déjà triées. C'est exactement le même principe.
« Liste initiale : [5, 2, 9, 1]. On prend le 2, on le compare au 5, on l'insère avant : [2, 5, 9, 1]. Puis le 9 reste à sa place. Enfin le 1 est inséré au début : [1, 2, 5, 9]. »
Point fort : L'élément courant est inséré dans la partie gauche déjà triée en décalant les plus grands vers la droite.
Complexité : dans le pire des cas (liste triée en ordre inverse), chaque insertion demande de décaler tous les éléments déjà triés, soit O(n²) comparaisons. En moyenne, c'est aussi O(n²). En revanche, si la liste est déjà presque triée, il est très rapide (O(n)).
✔️ A retenir
Le tri par insertion est simple et efficace sur de petites listes ou des listes presque triées. Sa complexité est quadratique dans le pire cas.
Tri fusion
Le tri fusion utilise la stratégie « diviser pour régner ». On coupe la liste en deux moitiés, on trie chaque moitié récursivement, puis on fusionne les deux moitiés triées.
La fusion consiste à comparer les premiers éléments des deux sous-listes et à placer le plus petit dans la liste résultat, jusqu'à épuisement des deux listes.
« Liste : [3, 1, 4, 2]. On coupe en [3, 1] et [4, 2]. On trie chaque moitié : [1, 3] et [2, 4]. Fusion : on compare 1 et 2, on prend 1 ; puis 3 et 2, on prend 2 ; puis 3 et 4, on prend 3 ; enfin 4. »
Point fort : La fusion se fait en une seule passe linéaire sur les deux sous-listes.
Complexité : le tri fusion a toujours une complexité en O(n log n), que la liste soit déjà triée ou non. Il nécessite un espace mémoire supplémentaire pour stocker les sous-listes lors de la fusion (O(n)).
✔️ A retenir
Le tri fusion est stable et a une complexité optimale en O(n log n). Son inconvénient est l'utilisation de mémoire supplémentaire.
Tri rapide (quicksort)
Le tri rapide utilise aussi « diviser pour régner ». On choisit un élément appelé pivot. On partitionne la liste en deux : les éléments plus petits que le pivot à gauche, les plus grands à droite. On trie récursivement chaque partie.
Le choix du pivot est crucial. Un mauvais choix (par exemple toujours le premier élément sur une liste déjà triée) peut dégrader la complexité.
« Liste : [8, 3, 5, 1, 9]. On choisit 5 comme pivot. Partition : [3, 1] (plus petits) et [8, 9] (plus grands). On trie chaque partie : [1, 3] et [8, 9]. Résultat final : [1, 3, 5, 8, 9]. »
Point fort : Le pivot 5 permet de séparer la liste en deux parties équilibrées, ce qui donne une bonne performance.
Complexité : en moyenne, le tri rapide est en O(n log n). Dans le pire des cas (pivot toujours minimal ou maximal), il devient O(n²). En pratique, il est souvent plus rapide que le tri fusion car il travaille en place (sans mémoire supplémentaire significative).
✔️ A retenir
Le tri rapide est très efficace en moyenne (O(n log n)) et travaille en place. Son pire cas est quadratique, mais on peut l'éviter avec un bon choix de pivot.
Comparaison des trois tris
Voici un tableau récapitulatif des complexités et caractéristiques des trois algorithmes.
Le tri par insertion est simple et efficace sur de petites listes. Le tri fusion est fiable et stable, mais gourmand en mémoire. Le tri rapide est très rapide en moyenne et économique en mémoire, mais instable et sensible au choix du pivot.
⚠️ Attention
Attention : la stabilité signifie que l'ordre relatif des éléments égaux est conservé. Le tri rapide ne l'est pas, ce qui peut être important dans certains contextes.
Implémentation en Python
Voici des squelettes d'implémentation pour chaque tri. Tu dois les compléter et les tester.
Pour le tri par insertion, on utilise une boucle for et une boucle while pour décaler les éléments. La fonction tri_insertion(liste) modifie la liste en place.
Pour le tri fusion, on écrit une fonction fusion(gauche, droite) qui retourne une nouvelle liste triée, et une fonction tri_fusion(liste) qui appelle récursivement.
Pour le tri rapide, on implémente une fonction partition(liste, debut, fin) qui place le pivot à sa bonne position et retourne son indice. La fonction tri_rapide(liste, debut, fin) s'appelle récursivement sur les deux sous-parties.
✔️ A retenir
Entraîne-toi à écrire ces trois algorithmes sans regarder le code. C'est un exercice classique au bac.
