Cours Tri par insertion
QCM
  • 1
  • 2
  • 3
  • 4
  • 5

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]

En effet, si on fait tourner cet algorithme avec cette fonction, on obtient une liste triée en sortie. 

[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.