L'énoncé
Répondre aux questions suivantes
Tu as obtenu le score de
Question 1
On propose la fonction de tri suivante :
def tri_inser(L): n = len(L) for i in range(0, n-1): k = i + 1 new = L[k] while new < L[k-1] and k >= 0: L[k] = L[k-1] k = k - 1 L[k] = new
Si L=[1, 4, 5, 2, 9] que retourne tri_inser(L) ?
Un message d'erreur
[1, 2, 4, 5, 9]
[5, 2, 9, 4, 1]
Question 2
On propose la fonction de tri suivante :
def tri_inser(L): n = len(L) for i in range(0, n-1): k = i + 1 new = L[k] while new < L[k-1] and k >= 0: L[k] = L[k-1] k = k - 1 L[k] = new
Si L=[4, 1, 5, 2, 9] que retourne tri_inser(L) ?
Un message d'erreur
[1, 2, 4, 5, 9]
[5, 2, 9, 4, 1]
Regardons ce qu'il se passe lors de la première itération de la boucle for.k prend la valeur 1. Il faut donc placer correctement la valeur L[1] c'est à dire la valeur 1.
La condition 1 < 4 est remplie, la liste devient alors [4, 4, 5, 2, 9] et k prend la valeur 0.
On compare ensuite 1 avec L[k-1] = L[-1] qui est égal à 9. La condition 1 < 9 est donc remplie. La liste devient alors [9, 4, 5, 2, 9] et k prend la valeur -1.
La condition k positif n'est donc plus remplie, la liste devient donc [9, 4, 5, 2, 1].
En continuant le raisonnement, on montre que la liste à l'issue de l'algorithme vaut [5, 2, 9, 4, 1].
L'hypothèse initiale qui n'est pas vérifiée ici est que les k premières valeurs de la liste ne sont pas triées car on autorise k à prendre la valeur 0.
On pourra faire tourner cet algorithme.
Pour rappel, L[-1] est égal au dernier élément de la liste L.
Question 3
On propose la fonction de tri suivante :
def tri_inser(L): n = len(L) for i in range(0, n-1): k = i + 1 new = L[k] while new < L[k-1] and k > 0: L[k] = L[k-1] k = k - 1 L[k] = new
Si L=[4, 1, 2, 4, 4, 2, 9, 4] que retourne tri_inser(L) ?
Un message d'erreur
[4, 4, 4, 4, 4, 4, 4, 4]
[1, 2, 2, 4, 4, 4, 4, 9]
L'algorithme est le même que celui étudié en cours, la liste est donc triée.
[1, 2, 4, 4, 4, 2, 9, 4]
Quel changement constate-t-on par rapport à l'algorithme vu en cours ?
Question 4
On propose la fonction de tri suivante :
def tri_inser(L): n = len(L) for i in range(0, n): k = i + 1 new = L[k] while new < L[k-1] and k > 0: L[k] = L[k-1] k = k - 1 L[k] = new
Si L=[4, 1, 2, 4, 4, 2, 9, 4] que retourne tri_inser(L) ?
Un message d'erreur
En effet, $i$ varie de $0$ à $n - 1$, donc $k$ varie de $1$ à $n$, or l'élément d'indice $n$ d'une liste de taille $n$ n'existe pas.
[4, 4, 4, 4, 4, 4, 4, 4]
[1, 2, 2, 4, 4, 4, 4, 9]
[1, 2, 4, 4, 4, 2, 9, 4]
Quel changement constate-t-on ?
Question 5
Quel est l'argument fondamental pour la terminaison de l'algorithme ?
Les termes de la liste sont toujours positifs.
$k$ prend ses valeurs dans une suite strictement décroissante minorée.
A chaque itération, k décroit forcément de 1, ainsi, k atteint forcément la valeur 0 donc la boucle while se termine toujours.
une boucle while se termine toujours.
Revoir la vidéo.
En effet, si on fait tourner cet algorithme avec cette fonction, on obtient une liste triée en sortie.