QCM

Invariant d'un algorithme de tri par insertion :

On considère un algorithme de tri par insertion, dans lequel la fonction:
echanger(tab[i], tab[j])

effectue l'échange les ième et jième valeurs du tableau tab.

nom: tri_insertion

paramètre: tab, tableau de n entiers, n >= 2

Traitement:
pour i allant de 2 à n:
j = i
tant que j > 1 et tab[j-1] > tab[j]:
echanger(tab[j-1], tab[j])
j = j-1
renvoyer tab

Question: quel est l'invariant de boucle qui correspond précisément à cet algorithme ?

A : Tous les éléments d'indice compris entre 0 et i sont triés et les éléments d'indice supérieurs ou égal à i leurs sont tous supérieurs
B : Tous les éléments d'indice supérieur ou égal à i sont triés par ordre croissant
C : Tous les éléments d'indice compris entre 0 et i sont triés, on ne peut rien dire sur les éléments d'indice supérieur ou égal à i
D : Tous les éléments d'indice supérieur ou égal à i sont non triés par ordre croissants