Même travail avec tri insertion sur le même tableau

Exercice de TD · niveau 2 · NSI (première), chapitre 7 — Parcourir, trier, prouver · Les deux tris, leurs invariants, leur coût

Énoncé

Même travail avec tri_insertion sur le même tableau. Combien de comparaisons chacun a-t-il effectuées ?

Corrigé

Sur [5, 2, 8, 1], en notant après chaque tour de la boucle externe :

$i$	carte insérée	état après	partie triée
---	---	`[5, 2, 8, 1]`	`[5]`
$1$	$2$	`[2, 5, 8, 1]`	`[2, 5]`
$2$	$8$	`[2, 5, 8, 1]`	`[2, 5, 8]`
$3$	$1$	`[1, 2, 5, 8]`	`[1, 2, 5, 8]`

Vérification de l'invariant : à chaque ligne, la partie t[0..i] est bien triée. Au tour $i = 2$ le tableau ne bouge pas — $8$ est déjà à sa place, la boucle interne ne fait aucun tour.

Le décompte des comparaisons.

	comparaisons	écritures
`tri_insertion`	$5$	$4$ décalages
`tri_selection`	$6$	$3$ échanges

L'insertion en fait $5$ : une au tour $1$ (  $5 > 2$  ), une au tour $2$ (  $5 > 8$ est faux, arrêt immédiat ), trois au tour $3$ . La sélection en fait exactement $4 \times 3/2 = 6$ , quel que soit le tableau.

Rappel du déroulé de la sélection, à comparer ligne à ligne : [5, 2, 8, 1], puis [1, 2, 8, 5], puis [1, 2, 8, 5], puis [1, 2, 5, 8].

Ce que la comparaison montre. Les deux tris arrivent au même tableau par des chemins différents : la sélection amène le bon élément à la bonne place, l'insertion amène la bonne place au bon élément. Et l'insertion a fait moins de comparaisons — parce que le tableau n'était pas trop désordonné. Sur [4, 3, 2, 1], elle en ferait $6$ , autant que la sélection.

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.