L'énoncé
Répondre aux questions suivantes
Tu as obtenu le score de
Question 1
Le tri par insertion est le seul tri qui permet de trier des listes.
Vrai
Faux
Question 2
Quelle hypothèse est faite à chaque étape ?
Les $k$ premières valeurs sont triées.
Au début de chaque itération, les $k$ premières valeurs sont triées et on place la $k+1$-ième à sa juste place parmi les $k$ valeurs.
Les $k$ dernières valeurs sont triées.
Les éléments sont tous positifs.
Question 3
On place la $(k + 1)$-ième valeur dans les $n$ valeurs qui composent la liste.
Vrai
Faux
Au début de chaque itération, les $k$ premières valeurs sont triées et on place la $k+1$-ième à sa juste place parmi les $k$ premières valeurs.
Question 4
Comment s'appelle l'élément que l'on doit placer lors d'une itération dans l'algorithme ?
k
L[k]
C'est vrai au début mais plus lors de la boucle while.
new
Cette variable contient la valeur que l'on doit placer correctement parmi les $k$ premières valeurs triées.
Question 5
Comment peut s'appeler new, la variable à placer lors d'une itération ?
la clé
On appelle l'élément à placer la clé.
old
new_one
Question 6
Que permet la condition $k > 0$ dans la boucle while ?
S'assurer que les éléments de la liste restent positifs
S'assurer que la liste soit triée dans le sens croissant
S'assurer que l'algorithme ne sorte pas de la liste
On parcourt la liste en partant du $k$-ième élément jusqu'au premier élément de la liste, d'indice $0$. On ne peut donc pas placer un élément plus loin que l'indice 0, or $k$ correspond à l'indice courant : il doit donc être positif.
Question 7
L'algorithme se termine forcément.
Vrai
La terminaison de l'algorithme nous montre que l'algorithme se compose de deux boucles : une boucle for qui se compose d'un nombre de passages fini et une boucle while avec au plus $i + 1$ passages. Le nombre de passages est donc fini.
Faux
Question 8
La complexité de cet algorithme de tri ne peut pas être linéaire.
Vrai
Faux
Si la liste est déjà triée, i prend n - 1 valeurs et à chaque itération il n'y a qu'une comparaison. La complexité est donc linéaire.
Question 9
Quelle est la complexité dans le pire des cas ?
$\mathcal{O}(n)$
$\mathcal{O}(n\ln(n))$
$\mathcal{O}(n^2)$
La complexité dans le pire des cas est en $\mathcal{O}(n^2)$, lorsque la liste est triée dans l'ordre décroissant.
Question 10
Dans quel cas le tri par insertion est-il efficace ?
Lorsque la liste est mal triée
Lorsque la liste est relativement bien triée
Lorsque la liste est relativement bien triée, l'algorithme fait peu de comparaisons ce qui permet de ne pas être trop couteux en temps de calcul.
Lorsque la liste ne contient que des éléments positifs.
En effet, il existe d'autres tris comme le tri par sélection...