On démontre qu'aucun tri fondé sur des comparaisons ne peut faire…

Exercice supplémentaire · niveau 3 (difficile) · NSI (première), chapitre 7 — Parcourir, trier, prouver · Ce que coûte un tri : bornes et mesures

Énoncé

On démontre qu'aucun tri fondé sur des comparaisons ne peut faire moins de $lo g_{2} (n!)$ comparaisons dans le pire cas. Comparer cette borne à $n lo g_{2} n$ et au coût du tri par sélection.

Corrigé

L'idée de la borne. Un tri par comparaisons doit pouvoir distinguer les $n!$ ordres possibles du tableau. Chaque comparaison rend un bit d'information — vrai ou faux. Avec $c$ comparaisons on distingue au plus $2^{c}$ cas ; il faut donc $2^{c} \geq n!$ , c'est-à-dire $c \geq lo g_{2} (n!)$ . C'est exactement le raisonnement « combien de bits faut-il ? » du chapitre 1, appliqué non à un entier mais à un nombre de possibilités.

$n$	$lo g_{2} (n!)$	$n lo g_{2} n$	$n (n - 1) /2$
$10$	$21, 8$	$33, 2$	$45$
$100$	$524, 8$	$664, 4$	$4950$
$1000$	$8529, 4$	$9965, 8$	$499500$

Trois enseignements.

La borne et $n lo g_{2} n$ sont du même ordre : leur rapport vaut $0, 66$ pour $n = 10$ , $0, 79$ pour $n = 100$ , $0, 86$ pour $n = 1000$ , $0, 89$ pour $n = 10000$ — il monte lentement vers $1$ . Un tri en $n lo g_{2} n$ est donc optimal à un facteur constant près : on ne fera jamais fondamentalement mieux.
Le tri par sélection en est très loin : $4950$ comparaisons pour $n = 100$ , contre une borne de $525$ . Il fait presque dix fois le minimum, et l'écart croît avec $n$ .
Le tri par comptage de l'exercice précédent fait $n + k$ , donc bien moins que $lo g_{2} (n!)$ — sans contredire le théorème, puisqu'il ne compare rien. La borne ne s'applique qu'aux tris par comparaison, et c'est la seule échappatoire.

Ce que cet exercice a d'inhabituel. On y démontre qu'un problème a un coût minimal, quel que soit l'algorithme — y compris ceux que personne n'a encore inventés. C'est un résultat sur le problème, non sur une solution, et c'est un genre de raisonnement qu'on ne rencontre plus avant les études supérieures.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.