Tri par sélection du minimum

On considère l'algorithme suivant prenant en paramètre un tableau tab d'entiers non vide.

fonction triSelection(tab):
    i ← 0 

    tant que i < longueur(tab)-1:

        j = indice dans tab d'un élément minimum de tab[i..]
        on échange les valeurs de tab[i] et tab[j]
        i ← i+1

Justifier que la boucle termine.

Indication

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

Réponse

Soit n = longueur(tab).

L'entier m = n - i est un variant de boucle.

Les valeurs de m sont en effet entières et positives dans la boucle. Et i croît strictement à chaque passage dans la boucle, donc m décroît strictement à chaque passage dans la boucle.