Exercice 3 - Tri par insertion

Nous allons écrire et démontrer la validité de l'algorithme du tri par insertion. Nous rappelons que $T = [T_1, \ldots, T_n]$ est trié si $\forall i \in \{1, \ldots, n-1\}, T_i \leq T_{i + 1}$. Etant donné le programme suivant :

Prouver que si on passe en paramètre à $insere$ un tableau $T$ dont les $k-1$ premiers éléments sont triés, alors à la fin de son exécution, les $k$ premiers éléments dont triés. Etant donné le programme suivant :

Démontrer la terminaison et la validité de $triInsertion$.

Voici le corrigé de la première question : L'algorithme se termine bien car les valeurs prises par $i$ forment une séquence de nombres entiers strictement décroissante. Si l'on ne sort pas de la boucle avec $T_{i-1} \leq T_i$, on aura forcément $i=1$ après la dernière itération. Prenons comme invariant de boucle la conjonction des conditions suivantes :

• La tranche $T_1, \ldots, T_{i-1}$ est triée
• La tranche $T_{i}, \ldots, T_{k}$ est triée
• $i<k \Rightarrow T_{i-1} \leq T_{i+1}$

Prouvons cette propriété par récurrence :

• A la première itération, on a $i=k$. Comme $T_1, \ldots, T_{i}$ correspond à la tranche $T_1, \ldots, T_{k-1}$ donc par hypothèse cette tranche est triée. La tranche $T_{i}, \ldots, T_{k}$ est réduite au seul élément $T_k$, elle est donc nécessairement triée. Comme $\neg(i < k)$, la troisième condition est trivialement vérifiée.
• Supposons qu'au début d'une itération arbitraire, les trois propriétés soient vérifiées. Soient $i^\prime$ la valeur de $i$ et $T^\prime$ le tableau $T$ à la fin de cette itération. Montrons alors que
  • La tranche $T^\prime_1, \ldots, T^\prime_{i^\prime-1}$ est triée
  • La tranche $T^\prime_{i^\prime}, \ldots, T^\prime_{k}$ est triée
  • $i^\prime < k \Rightarrow T^\prime_{i^\prime-1} \leq T^\prime_{i^\prime+1}$
  D'une part, on a $i>1$ et $T_{i-1} > T_{i}$. Par ailleurs, $i^\prime = i - 1$, $T^\prime_{i - 1} = T_i$ et $T^\prime_i = T_{i - 1}$. Tous les autres éléments de $T$ et de $T^\prime$ coïncident. Montrons les trois propriétés :
  • Par hypothèse de récurrence, la tranche $T_1, \ldots, T_{i-1}$ est triée, donc la tranche $T_{1}, \ldots, T_{i-1}$ que l'on obtient en ne comptabilisant pas le dernier élément est aussi triée. Comme les éléments de $T$ et $T^\prime$ d'indices différents de $i$ et $i+1$ sont les mêmes et que $i-1 = i^\prime$, alors $T^\prime_{1}, \ldots, T^\prime_{i^\prime}$ est triée.
  • Par hypothèse de réccurrence $T_{i}, \ldots, T_{k}$ est triée, en ne considérant pas le premier élément, on a $T_{i+1}, \ldots, T_{k}$, comme les éléments de cette tranche coïncident avec $T^\prime$, alors $T^\prime_{i^\prime+2}, \ldots, T^\prime_{k}$ est triée. Par ailleurs, on a $T^\prime_{i^\prime} = T_{i}$ et $T^\prime_{i^\prime + 1} = T_{i - 1}$, comme $T_{i-1} > T_{i}$, alors $T^\prime_{i^\prime} < T^\prime_{i^\prime + 1}$. Si $i < k$, alors par hypothèse de récurrence, on a $T_{i-1} \leq T_{i+1}$, donc $T^\prime_{i^\prime+1} \leq T^\prime_{i^\prime+2}$. Dans ce cas, on a $T^\prime_{i^\prime} < T^\prime_{i^\prime + 1} \leq T^\prime_{i^\prime + 2}$ avec $T^\prime_{i^\prime+2}, \ldots, T^\prime_{k}$ triée. Donc $T^\prime_{i^\prime}, \ldots, T^\prime_{k}$ est triée. Si $i=k$, alors la tranche $T^\prime_{i^\prime}, \ldots, T^\prime_{k}$ est réduite aux deux éléments $T^\prime_{i^\prime} < T^\prime_{i^\prime + 1}$, elle est donc triée.
  • Quelle que soit la valeur de $i$, on a nécessairement $i^\prime<k$, il faut donc montrer que $T^\prime_{i^\prime-1} \leq T^\prime_{i^\prime+1}$. Or $T^\prime_{i^\prime-1}= T_{i - 2}$ et $T^\prime_{i^\prime + 1} = T_{i - 1}$. Par hypothèse de récurrence, $T_1, \ldots, T_{i-1}$ est triée, donc on a $T_{i - 2} \leq T_{i-1}$, d'où $T^\prime_{i^\prime-1} \leq T^\prime_{i^\prime+1}$.

Après la denière itération, si $i=1$, alors la première tranche ne contient aucun élément et la deuxième condition de l'invariant de boucle permet de conclure que toute la tranche $T_1, \ldots, T_k$ est triée. Si par contre, on sort de la boucle parce que $T_{i-1} \leq T_{i}$, alors comme, d'après l'invariant de boucle, $T_1, \ldots, T_{i-1}$ et $T_{i}, \ldots, T_{k}$ sont triées, alors $T_1, \ldots, T_{k}$ est triée.