Le tri d’une liste est l’un des problèmes algorithmiques les plus fondamentaux en informatique. En prépa ECG, il apparaît régulièrement dans les sujets d’informatique, aussi bien pour tester la maîtrise des boucles et de la récursivité que pour illustrer les notions de complexité. Python dispose certes de la fonction ‘sorted’ et de la méthode ‘.sort()’, mais comprendre comment fonctionnent les algorithmes de tri et surtout pourquoi certains sont bien plus efficaces que d’autres est une compétence fondamentale, notamment pour les concours. Dans cet article, nous allons implémenter et analyser les trois principaux algorithmes : le tri à bulles, le tri par insertion et le tri fusion, avant de les comparer empiriquement.
Le tri à bulles
Principe
Le tri à bulles est l’algorithme de tri le plus intuitif. Il consiste à parcourir la liste en comparant chaque paire d’éléments adjacents et en les échangeant s’ils sont dans le mauvais ordre.
On répète ce processus jusqu’à ce que la liste soit triée. À chaque passage, le plus grand élément non encore placé « remonte » à sa position finale comme le ferait une bulle, d’où le nom de cette méthode.
Voici ci-dessous une manière d’implémenter ce type de tri de liste.
Implémentation
On commence par copier la liste avec ‘lst.copy()’ pour ne pas modifier la liste originale. La boucle externe sur ‘i’ représente le numéro du passage.
Après le \(i\)-ème passage, les \(i\) plus grands éléments sont déjà à leur place définitive en fin de liste, ce qui explique que la boucle interne ne parcourt que jusqu’à ‘n – 1 – i’.
L’échange ‘lst[j], lst[j + 1] = lst[j + 1], lst[j]’ réalisé si l’élément d’avant est supérieur à l’élément suivant permet de permuter deux éléments en une seule ligne, sans variable temporaire.
Complexité
Pour le pire cas, la liste est triée en ordre inverse : chaque comparaison entraîne un échange, et aucune optimisation n’est possible.
> Au passage \(i = 0\), la boucle interne effectue \(n – 1\) comparaisons.
> Au passage \(i = 1\), elle en effectue \(n – 2\).
> Au passage \(i = k\), elle en effectue \(n – 1 – k\).
> Au dernier passage \(i = n – 2\), elle en effectue \(1\).
Le nombre total de comparaisons est donc :
\[(n-1) + (n-2) + \cdots + 2 + 1 = \sum_{k=1}^{n-1} k = \frac{(n-1)n}{2}\]
Cette somme est la somme des \(n-1\) premiers entiers, que l’on calcule avec la formule classique \(\sum_{k=1}^{p} k = \frac{p(p+1)}{2}\) appliquée à \(p = n-1\).
Pour conclure en complexité, on a \(\frac{(n-1)n}{2} = \frac{n^2 – n}{2}\). Quand \(n\) devient grand, le terme dominant est \(\frac{n^2}{2}\) et le terme \(-\frac{n}{2}\) devient négligeable devant lui.
Par définition de la notation \(O\), cela veut dire que le nombre de comparaisons est en \(O(n^2)\). Par exemple, multiplier la taille de la liste par \(2\) multiplie le temps d’exécution par environ \(4\), et multiplier par \(10\) le multiplie par environ \(100\).
Le tri par insertion
Principe
Pour vulgariser le tri par insertion, il faut voir cette méthode comme s’inspirant de la façon dont on trie naturellement des cartes à jouer. On prend les éléments un par un et on insère chacun à la bonne position dans la partie déjà triée.
À l’étape \(i\), les \(i\) premiers éléments sont triés entre eux, et on insère le \((i+1)\)-ème à sa place dans la liste des \(i\) premiers.
Voici ci-dessous une manière d’implémenter cela en Python.
Implémentation
À chaque itération, on stocke l’élément courant dans ‘cle’. La boucle ‘while’ décale vers la droite tous les éléments de la partie triée qui sont plus grands que ‘cle’, en ouvrant une place pour l’insérer. Quand la boucle s’arrête, ‘j + 1’ est la position correcte pour ‘cle’.
Attention, cependant ! Il faut bien initialiser ‘j = i – 1’ et non ‘j = i’, sinon on comparerait ‘cle’ avec lui-même.
Complexité
Dans le pire cas, la liste est triée en ordre décroissant. Chaque nouvel élément cle est plus petit que tous ceux déjà triés, donc la boucle while doit décaler tous les éléments précédents pour l’insérer en première position.
À l’étape \(i = 1\), la boucle effectue une comparaison. Lorsque \(i = 2\), elle en effectue deux. À l’étape \(i = k\), elle en effectue \(k\). À l’étape \(i = n-1\), elle en effectue \(n-1\).
Le nombre total de comparaisons est donc :
\[1 + 2 + \cdots + (n-1) = \sum_{k=1}^{n-1} k = \frac{n(n-1)}{2}\]
On retrouve exactement la même somme que pour le tri à bulles, d’où la complexité en \(O(n^2)\) dans le pire cas.
Le tri fusion
Principe
Le tri fusion repose sur le fait de diviser la liste en deux moitiés. On trie récursivement chaque moitié, puis on fusionne les deux moitiés triées.
La fusion de deux listes triées est une opération linéaire. On compare les premiers éléments des deux listes et on prend le plus petit, puis on recommence jusqu’à épuisement des deux listes.
Implémentation
La fonction ‘fusionner’ construit la liste résultat en comparant les éléments tête à tête. Quand l’une des deux listes est épuisée, on ajoute directement le reste de l’autre avec ‘resultat += gauche[i:]’ ou ‘resultat += droite[j:]’, ce qui est équivalent à une boucle, mais bien plus concis.
La fonction ‘tri_fusion’ est récursive : le cas de base est une liste de taille \(\leq 1\), déjà triée par définition. Pour le cas général, on divise au milieu avec ‘len(lst) // 2’ (division entière), on trie chaque moitié récursivement, et on fusionne.
Complexité
L’arbre de récursion du tri fusion a la structure suivante : au niveau \(0\), on a une liste de taille \(n\). Au niveau \(1\), deux listes de taille \(\frac{n}{2}\). Au niveau \(2\), quatre listes de taille \(\frac{n}{4}\). Dès lors, pour \(k\), \(2^k\) listes de taille \(\frac{n}{2^k}\). La récursion s’arrête quand les listes sont de taille \(1\), c’est-à-dire quand \(\frac{n}{2^k} = 1\), soit \(k = \log_2 n\). Le nombre de niveaux est donc exactement \(log_2 n\).
Au niveau \(k\), on fusionne \(2^k\) paires de listes de taille \(\frac{n}{2^{k+1}}\) chacune. La fusion de deux listes de taille \(p\) et \(q\) effectue au plus \(p + q\) comparaisons : on parcourt les deux listes une seule fois de gauche à droite. Chaque paire de listes fusionnées produit une liste de taille \(\frac{n}{2^k}\), et le coût de cette fusion est \(\frac{n}{2^k}\). Comme il y a \(2^k\) fusions au niveau \(k\), le coût total à ce niveau est :
\(2^k \times \frac{n}{2^k} = n\)
Il y a \(\log_2 n\) niveaux, chacun coûtant \(n\) opérations. Le coût total est donc :
\[n \times \log_2 n = O(n \log n)\]
C’est d’ailleurs la complexité optimale pour un algorithme de tri par comparaison : on peut démontrer qu’aucun algorithme de ce type ne peut faire mieux que \(O(n \log n)\) dans le pire cas. Nous ne réaliserons cependant pas cette démonstration qui s’écarte du cœur de cet article.
Comparaison empirique
Mesure des temps d’exécution
On compare les trois algorithmes sur des listes de tailles croissantes en mesurant leur temps d’exécution avec le module ‘time’.
Résultats et interprétation
Pour \(n = 100\), les trois algorithmes sont comparables et quasi instantanés.
Avec \(n = 1000\), le tri à bulles est déjà nettement plus lent que le tri par insertion, lui-même nettement plus lent que le tri fusion. En prenant \(n = 2000\), l’écart se creuse encore : multiplier \(n\) par 2 multiplie le temps des algorithmes en \(O(n^2)\) par environ 4, tandis que le tri fusion ne voit son temps que légèrement augmenter conformément à \(O(n \log n)\).
Synthèse
- Tri à bulles : \(O(n^2)\) dans tous les cas. Simple à comprendre et à implémenter, utile uniquement pour illustrer le concept de tri en cours, mais peu utilisé en pratique.
- Tri par insertion : \(O(n^2)\) dans le pire cas, \(O(n)\) dans le meilleur cas. Efficace sur les listes presque triées, utilisé en pratique pour de petites listes.
- Tri fusion : \(O(n \log n)\) dans tous les cas. Optimal en complexité, utilisé en pratique pour de grandes listes. C’est d’ailleurs l’algorithme sur lequel repose la fonction ‘sorted’ de Python (avec des optimisations supplémentaires réalisées en interne par rapport à la fonction que nous venons de voir).
Conclusion
En définitive, l’étude comparative des algorithmes de tri illustre parfaitement l’importance de la complexité algorithmique : deux algorithmes qui produisent le même résultat peuvent avoir des performances radicalement différentes selon la taille des données.
Le tri fusion, avec sa complexité \(O(n \log n)\) garantie, est optimal au sens théorique. En concours, savoir implémenter le tri par insertion et le tri fusion, expliquer leur complexité respective et justifier pourquoi \(O(n \log n)\) est optimal pour un tri par comparaison sont trois compétences directement évaluables.
Il n’y a plus qu’à croiser les doigts pour qu’un tel thème tombe aux concours !
Tu peux retrouver ici le méga-répertoire qui contient toutes les annales de concours et les corrigés. Tu peux également accéder ici à toutes nos autres ressources mathématiques !
