Pourquoi la boucle externe de tri selection s'arrête-t-elle à n - 1 et…

Application directe du cours · niveau 2 · NSI (première), chapitre 7 — Parcourir, trier, prouver · Dérouler, compter, vérifier

Énoncé

Pourquoi la boucle externe de tri_selection s'arrête-t-elle à n - 1 et non à n ? Que se passerait-il avec n — erreur, ou simple travail inutile ?

Corrigé

Pourquoi $n - 1$ suffit. C'est la troisième étape de la démonstration du cours. À la sortie, t[0..n-2] est trié et contient les $n - 1$ plus petits éléments ; le seul élément restant est donc le plus grand, et la seule case restante est la dernière. Il y est déjà. Il n'y a rien à faire.

Avec n : du travail inutile, et rien d'autre. Au tour $i = n - 1$ , la boucle interne est range(n, n) — vide. Aucune comparaison n'est faite, m reste égal à $n - 1$ , et l'échange t[n-1], t[n-1] = t[n-1], t[n-1] ne change rien.

$n$	comparaisons, boucle à $n - 1$	boucle à $n$
$1$	$0$	$0$
$2$	$1$	$1$
$10$	$45$	$45$
$100$	$4950$	$4950$

Exactement le même nombre de comparaisons — et les deux versions rendent le même tableau, vérifié sur $2000$ tirages. Le coût supplémentaire est d'un tour de boucle et d'un échange nul : invisible.

Ce qui serait, en revanche, une vraie erreur. Écrire range(n + 1) : au tour $i = n$ , l'accès t[n] lèverait une IndexError. Et le cas $n = 0$ mérite un regard : range(-1) est vide, donc le tri d'un tableau vide ne fait rien — ce qui est juste.

La conclusion à retenir. Écrire $n - 1$ n'est pas une optimisation : c'est ce que la démonstration dit. Une borne de boucle qu'on ne sait pas justifier est une borne qu'on a devinée — et un jour on devinera mal.

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.