Écrire la variante du tri par sélection qui cherche le maximum et le…

def tri_selection_max(t):
    """Trie t en plaçant le maximum en fin de la partie non triée.

    Postcondition : t est croissant et contient les mêmes éléments.
    """
    n = len(t)
    for i in range(n - 1, 0, -1):
        # invariant : t[i+1..n-1] est trié et contient les
        #             n-1-i plus GRANDS éléments du tableau
        m = 0
        for j in range(1, i + 1):
            if t[j] > t[m]:
                m = j
        t[i], t[m] = t[m], t[i]

Validation : $3000$ tableaux tirés au hasard, comparés à sorted — $3000$ cas passent, tableaux vides et à un élément compris.

L'invariant est le miroir de celui du cours. La frontière part de la droite et recule ; ce qui est à sa droite est trié et définitif. Les trois étapes se mènent identiquement : initialisation ($i=n-1$, la partie droite est vide), conservation (le maximum de t[0..i] arrive en $i$, et il est $\ge$ à tout ce qui reste à gauche), terminaison ($i=1$ : t[1..n-1] est trié et contient les $n-1$ plus grands, donc t[0] est le plus petit et il est à sa place).

Le coût est identique, et pour une raison de comptage. Au tour $i$, la boucle interne fait $i$ comparaisons ; le total vaut

$$\sum _{i=1}^{n-1}i=\frac{n(n-1)}{2},$$

la même somme que dans le cours, écrite dans l'autre sens. Renverser un algorithme ne change pas son coût : c'est la même somme d'entiers, parcourue de l'autre bout.