Deux déroulés

Deux déroulés

Les tris · niveau 1 (application)

Énoncé

Dérouler le tri par sélection puis le tri par insertion sur le tableau $t = [4, 2, 5, 1]$ en comptant les comparaisons.

Sélection :
$i = 0$ : minimum de $[4, 2, 5, 1]$ est $1$ (indice $3$ ). Échange avec $4 ⟹ [1, 2, 5, 4]$ (3 comparaisons).
$i = 1$ : minimum de $[2, 5, 4]$ est $2$ (indice $1$ ). Déjà placé $⟹$ inchangé (2 comparaisons).
$i = 2$ : minimum de $[5, 4]$ est $4$ (indice $3$ ). Échange avec $5 ⟹ [1, 2, 4, 5]$ (1 comparaison). Total : $6$ comparaisons, $2$ échanges effectifs.
Insertion :
$i = 1$ : insérer $2$ dans $[4] ⟹ [2, 4, 5, 1]$ (1 comparaison).
$i = 2$ : insérer $5$ dans $[2, 4] ⟹ [2, 4, 5, 1]$ (1 comparaison, reste en place).
$i = 3$ : insérer $1$ dans $[2, 4, 5] ⟹ [1, 2, 4, 5]$ (3 comparaisons/décalages). Total : $5$ comparaisons.