Écrire minimum et maximum(t) en un seul parcours, renvoyant un couple

def minimum_et_maximum(t):
    """Couple (plus petit, plus grand) en un seul parcours.

    Précondition  : t est non vide.
    Postcondition : mini <= x <= maxi pour tout x de t, et mini et maxi
                    appartiennent tous deux à t.
    """
    assert len(t) > 0, "tableau vide"
    mini = maxi = t[0]
    for i in range(1, len(t)):
        if t[i] < mini:
            mini = t[i]
        else:
            if t[i] > maxi:
                maxi = t[i]
    return mini, maxi

L'invariant tient en une phrase : avant le tour $i$, mini et maxi sont le plus petit et le plus grand élément de t[0..i-1]. L'initialisation à t[0] — et non à une constante — est ce qui rend l'invariant vrai au départ, et c'est l'avertissement du cours.

Le décompte. Le else est essentiel : si t[i] est plus petit que le minimum, il ne peut pas être plus grand que le maximum, et la seconde comparaison est inutile. Le coût dépend donc du contenu :

• pire cas — tableau croissant : la première comparaison est toujours fausse, on paie les deux à chaque tour, soit $2(n-1)$. Mesuré sur $n=100$ croissant : 198 comparaisons, et $2\times 99=198$ ;
• meilleur cas — tableau décroissant : une seule comparaison par tour, soit $n-1$. Mesuré : 99.

Peut-on faire mieux ? Oui : $\lceil 3n/2\rceil -2$. On traite les éléments par paires. Une comparaison range les deux membres de la paire ; le plus petit ne peut alors concourir que pour le minimum, le plus grand que pour le maximum. Trois comparaisons par paire, soit $3/2$ par élément, au lieu de $2$.

Les deux versions ont été comparées sur $2000$ tableaux tirés au hasard : elles rendent toujours le même couple, et le même que (min(t), max(t)).

Ce que cela vaut, honnêtement. On passe de $2n$ à $1,5n$ : le gain est d'un quart, il ne change pas la loi — les deux restent linéaires. On peut démontrer qu'aucun algorithme ne descend sous $\lceil 3n/2\rceil -2$ comparaisons ; c'est donc l'optimum, et c'est un résultat de terminale.