Quickselect : la constante, et le pire cas

1. Mesures sur $300$ exécutions, tableaux de valeurs distinctes mélangées :

Le rapport au $n$ reste constant quand $n$ est multiplié par cent : la complexité est bien $\Theta (n)$ en espérance, et non $\Theta (n\log n)$. La constante mesurée, environ $3,4$, est celle que prévoit l'analyse : $2(1+\ln 2)\approx 3,386$ comparaisons par élément pour la médiane.

L'écart avec le tri se creuse : à $n=10^5$, on fait cinq fois moins de comparaisons. Trier pour lire un seul élément est exactement le genre de travail inutile que le chapitre chap:diviser apprend à repérer.

2. Le pire cas s'obtient en forçant le pivot à être l'élément minimal à chaque appel : chaque étape n'élimine qu'un élément, et l'on parcourt $n,n-1,n-2,\dots$ Pour $n=2000$, la mesure donne $2000999$ comparaisons, à comparer à

$$\frac{n(n+1)}{2}-1=\frac{2000\times 2001}{2}-1=2000999.$$

L'accord est exact — ce n'est pas une estimation, c'est le compte.

3. Parce que le pire cas ne dépend pas de l'entrée mais des tirages. Un adversaire qui connaît le code peut construire l'entrée qu'il veut ; il ne peut pas choisir les pivots, qui sont tirés à l'exécution. La suite de pivots la plus défavorable — le minimum du sous-tableau à chaque étape — a une probabilité

$$\frac{1}{n}\times \frac{1}{n-1}\times \cdots \times \frac{1}{1}=\frac{1}{n!},$$

soit environ $10^{-158}$ pour $n=100$.

C'est le vrai apport du hasard ici, et il vaut d'être formulé nettement. Un tri rapide à pivot fixe — le premier élément — a un pire cas en $\Theta (n^2)$ atteint par une entrée déjà triée, c'est-à-dire l'entrée la plus banale qui soit. En tirant le pivot au hasard, on ne supprime pas le pire cas : on le rend inatteignable par construction. C'est la dernière phrase du chapitre : le hasard protège du pire cas parce que l'adversaire ne connaît pas les tirages.