Tri par insertion

Question 1

On considère l'algorithme suivant dans lequel

• le paramètre tab est un tableau d'entiers (indices compris entre 0 et longueur(tab)-1))
• le paramètre i est un entier compris entre 1 et longueur(tab)-1 tel que tab[0..(i-1)] est trié en ordre croissant.

fonction descendre(tab, i):
    j ← i

    tant que j > 0 et tab[j] < tab[j-1]:

        on échange les valeurs de tab[j] et tab[j-1]
        j ← j-1   

Montrer que la boucle "tant que" de la fonction descendre termine.

Indication

Montrez que j est un variant de la boucle.

Une réponse

j est un variant de la boucle:

• j prend des valeurs entières positives dans la boucle.
• j décroît strictement à chaque passage dans la boucle (il est décrémenté d'une unité).

Donc la boucle termine.

Question 2

Le tri par insertion d'un tableau utilise la fonction descendre.

Le paramètre tab est un tableau (non vide) d'entiers.

fonction triInsertion(tab):
    i ← 1

    tant que i < longueur(tab):

        descendre(tab, i)
        i ← i+1

Démontrer que l'algorithme termine.

Indication

Montrez que n - i est un variant de la boucle (où n est la longueur de tab).

variant

Posons n = longueur(tab). n est fixe.
n - i est un variant:

• n et i sont entiers donc n - i est entier.
• Dans la boucle, on a i < n, donc n - i est positif.
• i augmente strictement à chaque passage dans la boucle, donc n - i diminue strictement à chaque passage dans la boucle.

L'algorithme termine donc.