Complexité du tri rapide : meilleur, moyen et pire cas

1. La Relation de Récurrence Générale du Tri Rapide

Pour analyser un algorithme récursif comme le tri rapide, nous devons d'abord établir sa relation de récurrence. Rappelez-vous les trois étapes de "diviser pour régner" :

1. Diviser : La fonction partition prend un temps proportionnel à la taille du sous-tableau, soit $\Theta (n)$. Elle divise le tableau en deux sous-problèmes.
2. Régner : Deux appels récursifs sont effectués sur les sous-tableaux. Si la partition place le pivot à l'indice k (créant un sous-tableau de taille k et un autre de taille n-k-1), le temps de cette étape est $T(k)+T(n-k-1)$.
3. Combiner : Cette étape est triviale et prend un temps constant, $\Theta (1)$.

En additionnant ces coûts, la complexité du tri rapide, $T(n)$, pour un tableau de taille $n$ peut s'écrire :

La performance de l'algorithme dépend entièrement de la valeur de $k$ à chaque appel, c'est-à-dire de l'équilibre des partitions générées par le pivot.

2. Analyse du Pire Cas : La Partition Déséquilibrée

Le pire scénario se produit lorsque le partitionnement est systématiquement le plus déséquilibré possible.

• Scénario : Cela arrive si le pivot choisi est toujours le plus petit ou le plus grand élément du sous-tableau. Par exemple, si vous appliquez un tri rapide avec le dernier élément comme pivot sur un tableau déjà trié. La partition produira un sous-tableau de taille $n-1$ et un autre de taille 0.

• Récurrence : En posant $k=n-1$ (ou $k=0$), la récurrence devient :

  $$T(n)=T(n-1)+T(0)+\Theta (n)=T(n-1)+\Theta (n)$$

Pour comprendre comment cette situation mène à une complexité quadratique, la vidéo suivante l'explique de manière très visuelle.

Formalisons cette analyse par la méthode de substitution, une technique fondamentale que vous devez maîtriser. En supposant $\Theta (n)=cn$ pour une constante $c>0$ :

L'arbre de récursion dans ce cas est complètement dégénéré, comme une simple liste.

Le pire cas est donc aussi mauvais que celui du tri par insertion. Cela souligne pourquoi le choix naïf du pivot (toujours le premier ou le dernier) est dangereux en pratique.

3. Analyse du Meilleur Cas : La Partition Parfaite

Le meilleur cas se produit lorsque chaque partition est la plus équilibrée possible.

• Scénario : Cela se produit si le pivot est toujours la médiane du sous-tableau. La partition divise alors le tableau en deux moitiés de taille à peu près égale, $\approx n/2$.

• Récurrence : La récurrence devient :

  $$T(n)=T(n/2)+T(n/2)+\Theta (n)=2T(n/2)+\Theta (n)$$

Cette récurrence vous est familière : c'est la même que celle du tri fusion.

Comme pour le tri fusion, la solution de cette récurrence est $\Theta (n\log n)$.

Bien que ce cas soit optimal, choisir la médiane comme pivot à chaque étape nécessite un algorithme de sélection en temps linéaire, ce qui compliquerait et ralentirait l'implémentation. La question est donc : que se passe-t-il entre ces deux extrêmes ?

4. Analyse du Cas Moyen : Le Cœur de la "Rapidité"

Le véritable intérêt du tri rapide réside dans sa performance moyenne exceptionnelle. L'analyse formelle est complexe, mais l'intuition est à la fois accessible et puissante.

Pourquoi le cas moyen est-il plus proche du meilleur cas que du pire ? L'idée clé est que nous n'avons pas besoin de partitions parfaitement équilibrées. Des partitions "raisonnablement" équilibrées suffisent.

Pour construire cette intuition, je vous propose de regarder la vidéo suivante qui l'aborde sous plusieurs angles.

Synthétisons et formalisons légèrement ces arguments :

Argument 1 : Toute partition à proportion constante est bonne

Imaginons un cas d'apparence défavorable où le pivot génère systématiquement une partition 9-contre-1. La récurrence est :

L'arbre de récursion sera asymétrique. La branche la plus longue (la plus profonde) déterminera la hauteur de l'arbre. Cette profondeur $h$ est atteinte lorsque $n\times (9/10{)}^h\approx 1$, soit $h\approx {\log }_{10/9}n$. Comme ${\log }_{10/9}n=\frac{\ln n}{\ln (10/9)}$, la hauteur est toujours $\Theta (\log n)$.

Le coût total reste borné par (coût par niveau) $\times$ (hauteur), soit $cn\times \Theta (\log n)=\Theta (n\log n)$.

Conclusion intuitive : Tant que le pivot n'est pas systématiquement dans les extrêmes, mais dans une zone "centrale" (même si elle est large, par ex. entre 1% et 99%), la profondeur de la récursion reste logarithmique, et la complexité globale reste $\Theta (n\log n)$. Pour un pivot choisi au hasard, la probabilité de tomber systématiquement dans les extrêmes est infime.

Argument 2 : L'analogie avec les arbres binaires de recherche (BST)

C'est un argument plus subtil. Considérez l'algorithme "BST-Sort" : insérer $n$ éléments dans un BST, puis faire un parcours infixe.

• Si les éléments sont insérés dans un ordre aléatoire, la hauteur moyenne de l'arbre est $\Theta (\log n)$, et le coût total de construction est en moyenne $\Theta (n\log n)$.
• Il s'avère que l'ensemble des comparaisons effectuées par le tri rapide avec pivot aléatoire sur un tableau est exactement le même que l'ensemble des comparaisons effectuées lors de l'insertion des mêmes éléments dans un ordre aléatoire dans un BST.

Cette équivalence profonde implique que la complexité moyenne du tri rapide est également $\Theta (n\log n)$.

Pour aller plus loin : la preuve formelle

Les arguments ci-dessus sont des intuitions. La preuve rigoureuse, exigible au niveau de l'Agrégation, utilise des outils de probabilités plus avancés (variables indicatrices et linéarité de l'espérance). Elle consiste à calculer, pour toute paire d'éléments $\{z_i,z_j\}$, la probabilité qu'ils soient comparés durant l'algorithme.

Je vous propose en lecture optionnelle (mais fortement recommandée) un document qui détaille cette preuve.

Conclusion

Nous avons maintenant une vision complète de la performance du tri rapide.

Points clés à retenir :

• Pire cas : $\Theta (n^2)$. Se produit avec des partitions totalement déséquilibrées (ex: tableau déjà trié avec un pivot naïf).
• Meilleur cas : $\Theta (n\log n)$. Se produit avec des partitions parfaitement équilibrées (pivot médian).
• Cas moyen (attendu) : $\Theta (n\log n)$. C'est le cas le plus important. Il s'explique par le fait que des partitions "moyennement" équilibrées suffisent à maintenir une profondeur de récursion logarithmique. Une randomisation du pivot rend le pire cas extrêmement improbable sur n'importe quelle entrée.

Le tri rapide est qualifié de "rapide" car sa complexité moyenne est excellente, et les constantes cachées dans la notation $\Theta$ sont généralement plus petites que celles de ses concurrents comme le tri fusion ou le tri par tas. De plus, son fonctionnement "en place" (si l'on ignore la pile de récursion) le rend très efficace en termes de localité de la mémoire.

Prochaine étape :
Dans la prochaine leçon, nous allons introduire une nouvelle structure de données fondamentale : le tas binaire (heap). Cette structure nous permettra de construire un autre algorithme de tri majeur, le tri par tas (heapsort), qui, contrairement au tri rapide, garantit une complexité en $\Theta (n\log n)$ dans tous les cas.