Question transversaleMathsNSIRécursivité et récurrence

Le tri rapide est quadratique dans le pire cas : pourquoi est-il pourtant si utilisé ?

Le tri rapide coupe la liste autour d'un pivot. Au pire, il fait n(n − 1)/2 comparaisons (499 500 pour n = 1 000) ; en moyenne, avec un pivot au hasard, environ 2n ln n, soit à peu près 11 000 pour n = 1 000. Le hasard rend le pire cas extrêmement improbable.

Grand oral session 2027 : exposé de 10 minutes debout, puis 10 minutes d'échange, sans calculatrice. Plan prévu pour 9,5 min.

Pourquoi cette question : un modèle d'introduction

Le jury attend que vous expliquiez pourquoi vous avez choisi la question. Inspirez-vous de ce modèle, mais racontez votre propre parcours.

En NSI, on nous a présenté le tri rapide comme l'un des tris les plus utilisés, puis on nous a dit que dans le pire cas il était aussi lent qu'un tri par sélection. Cela m'a semblé contradictoire. J'ai voulu comprendre comment un algorithme peut être à la fois lent au pire et rapide en pratique, et c'est l'espérance qui m'a donné la réponse.

L'enjeu et les notions du programme

Distinguer coût dans le pire cas et coût moyen, et utiliser les probabilités pour analyser un algorithme récursif.

Mathématiques

Variable aléatoire, espérance (première, terminale)
Somme d'une suite arithmétique (première)
Logarithme népérien (terminale)

Numérique et sciences informatiques

Méthode « diviser pour régner », récursivité (terminale)
Coût d'un algorithme (première)

Le plan de l'exposé en 9,5 min

1. Introduction
1 min
Le tri rapide choisit un élément, le pivot, place à sa gauche les éléments plus petits et à sa droite les plus grands, puis trie récursivement les deux parties. Problématique : son coût dépend-il du pivot, et que vaut-il en moyenne ?
2. Mathématiques : pire cas et cas moyen
4 min
Partitionner $n$ n éléments demande $n - 1$ n-1 comparaisons au pivot. Pire cas : le pivot est toujours le minimum (liste déjà triée et pivot pris en tête). Une partie est vide, l'autre a $n - 1$ n-1 éléments : $(n - 1) + (n - 2) + \dots + 1 = \frac{n ( n - 1 )}{2}$ (n-1)+(n-2)+…+1=(n(n-1))/2, soit $499500$ 499 500 pour $n = 1000$ n=1 000.
Cas favorable : le pivot coupe toujours en deux moitiés. On retrouve la récurrence du tri fusion, d'où environ $n lo g_{2} n \approx 10000$ nlog₂n≈10 000.
Cas moyen, avec un pivot tiré au hasard : deux éléments de rangs $i < j$ i<j sont comparés seulement si l'un d'eux est le premier pivot choisi parmi les éléments de rang $i$ i à $j$ j, ce qui arrive avec une probabilité $\frac{2}{j - i + 1}$ 2/(j-i+1). En additionnant ces probabilités (linéarité de l'espérance), on obtient environ $2 n ln n$ 2nln n comparaisons. Pour $n = 1000$ n=1 000, le calcul exact donne environ 11 000, à peine plus que le cas favorable.
3. NSI : pourquoi il est choisi
3 min
Le tri rapide trie « en place » : il n'a pas besoin de listes supplémentaires, contrairement au tri fusion. Sa partition est très rapide sur les processeurs modernes.
Pour éviter le pire cas, on choisit le pivot au hasard, ou on prend la médiane de trois éléments. La probabilité de tomber sur le pire cas devient astronomiquement faible. On mesure en Python : sur une liste triée de 2 000 éléments, le pivot en tête déclenche le pire cas (et même une erreur de profondeur de récursion), le pivot aléatoire non.
4. Conclusion
1,5 min
Le tri rapide est quadratique au pire, mais son coût moyen est d'environ $2 n ln n$ 2nln n, soit à peu près $1, 39 n lo g_{2} n$ 1,39 nlog₂n. En tirant le pivot au hasard, on rend le pire cas improbable : c'est un algorithme probabiliste. J'ouvre sur l'introsort, qui bascule sur un autre tri si la récursion devient trop profonde.

Ce que j'écris au tableau

Pas de calculatrice ni de support numérique : un calcul clé écrit au tableau rend l'exposé concret et montre la solidité des connaissances.

pire cas : \frac{n ( n - 1 )}{2} = 499500 (n = 1000) pire cas : (n(n-1))/2=499 500 (n=1000) P (i et j compar \overset{e}{ˊ} s) = \frac{2}{j - i + 1} E \approx 2 n ln n \approx 1, 39 n lo g_{2} n P(i et j comparés )=2/(j-i+1) E\approx2nln n\approx1,39 nlog₂n

Conclusion : la réponse à la question

Un algorithme se juge aussi par son coût moyen : le tri rapide, lent dans un cas très rare, est rapide en espérance. Les probabilités justifient le choix des informaticiens.

Les questions probables du jury

Pendant les 10 minutesd'échange, le jury vous fait préciser et approfondir, sur tout le programme de vos spécialités en lien avec la question.

Pourquoi n − 1 comparaisons pour partitionner ?

On compare chaque élément autre que le pivot au pivot, une fois.

Qu'est-ce que la linéarité de l'espérance ?

$E (X + Y) = E (X) + E (Y)$ E(X+Y)=E(X)+E(Y), même si $X$ X et $Y$ Y ne sont pas indépendantes : on additionne les probabilités de chaque comparaison.

Pourquoi 2n ln n ≈ 1,39 n log₂ n ?

$ln n = ln 2 \times lo g_{2} n$ ln n=ln2×log₂n, donc $2 n ln n = 2 ln 2 n lo g_{2} n \approx 1, 39 n lo g_{2} n$ 2nln n=2ln2 nlog₂n≈1,39 nlog₂n.

Quel est le pire cas avec un pivot en tête ?

Une liste déjà triée (ou triée à l'envers) : chaque partition est déséquilibrée au maximum.

Le tri fusion a-t-il un pire cas quadratique ?

Non : il coûte toujours de l'ordre de n log₂ n, mais demande de la mémoire supplémentaire.

Les pièges qui coûtent des points

Confondre pire cas et cas moyen.
Croire que le hasard rend le résultat aléatoire : seul le temps de calcul l'est, le tri est toujours correct.
Oublier que le pivot fixe est vulnérable aux listes déjà triées.

Revoir les notions

Autres questions : récursivité et récurrence

Toutes les questions maths-nsi →

Préparer l'oral, pas seulement le contenu

Gestion des 20 minutes de préparation, usage du tableau, posture debout, réponses au jury : la méthode complète, conforme aux règles de la session 2027.

Méthode : traiter une question de Grand oral →

Continuer la préparation

Le Grand oral 2027 →Méthode : traiter une question →Toutes les questions, par combinaison →Questions de maths seules →Questions maths-physique-chimie →Questions maths-SES →Questions maths-SVT →Questions maths-SI →Questions maths-HGGSP →Questions maths-anglais →