Dérouler à la main tri selection sur [5, 2, 8, 1] , en écrivant l'état…

Parcourir, trier, prouver · Dérouler, compter, vérifier · niveau 1 (application)

Énoncé

Dérouler à la main tri_selection sur [5, 2, 8, 1], en écrivant l'état du tableau après chaque tour, et vérifier l'invariant à chaque étape.

Corrigé

$i$	minimum de `t[i..3]`	échange	état après
—	—	—	`[5, 2, 8, 1]`
$0$	$1$ , en position $3$	`t[0]` $\leftrightarrow$ `t[3]`	`[1, 2, 8, 5]`
$1$	$2$ , en position $1$	`t[1]` $\leftrightarrow$ `t[1]`	`[1, 2, 8, 5]`
$2$	$5$ , en position $3$	`t[2]` $\leftrightarrow$ `t[3]`	`[1, 2, 5, 8]`

L'invariant, ligne à ligne — avant le tour $i$ , t[0..i-1] est trié et contient les $i$ plus petits éléments :

avant $i = 0$ : partie vide, vrai par vacuité ;
avant $i = 1$ : [1] — trié, et $1$ est bien le plus petit des quatre ;
avant $i = 2$ : [1, 2] — trié, et ce sont bien les deux plus petits ;
avant $i = 3$ , c'est-à-dire à la sortie : [1, 2, 5] — trié, et ce sont les trois plus petits. Le $8$ restant est donc le plus grand, et il est déjà à sa place.

Deux observations. Au tour $1$ , l'échange se fait de la case avec elle-même : c'est un travail nul, et le tri par sélection en fait souvent. Et à la fin, la boucle s'arrête à $i = 2$ , pas $3$ : la dernière case est juste par conséquence de l'invariant, non parce qu'on s'en est occupé. C'est le sujet de l'exercice suivant.

Le décompte : $6$ comparaisons — soit $4 \times 3/2$ — et $3$ échanges.