Instrumenter le tri par insertion pour compter ses comparaisons, et…


def tri_insertion_compte(t):
    """Comme tri_insertion, mais rend (comparaisons, décalages)."""
    comp = 0
    dec = 0
    for i in range(1, len(t)):
        x = t[i]
        j = i
        while j > 0:
            comp = comp + 1
            if t[j - 1] > x:
                t[j] = t[j - 1]
                j = j - 1
                dec = dec + 1
            else:
                break
        t[j] = x
    return comp, dec

$n$	trié	aléatoire	à l'envers	$n (n - 1) /2$
$10$	$9$	$29, 2$	$45$	$45$
$100$	$99$	$2559$	$4950$	$4950$
$200$	$199$	$10133$	$19900$	$19900$
$400$	$399$	$40311$	$79800$	$79800$

(colonne « aléatoire » : moyenne sur $400$ tirages par taille.)

Les trois rapports, quand $n$ double.

cas	rapports mesurés	loi
trié	$2, 01$ puis $2, 005$	linéaire, $n - 1$
aléatoire	$3, 96$ puis $3, 98$	quadratique
à l'envers	$4, 02$ puis $4, 01$	quadratique, $n (n - 1) /2$

Ce que les mesures confirment, et ce qu'elles ajoutent. Le meilleur cas double quand $n$ double, le pire quadruple : ce sont exactement les deux lois du cours. La colonne « à l'envers » vaut exactement $n (n - 1) /2$ , ce qui n'est pas une approximation mais une identité — chaque élément traverse toute la partie triée.

L'ajout, c'est la colonne aléatoire : elle quadruple aussi, donc elle est quadratique, mais elle vaut environ la moitié du pire cas ( $2559$ contre $4950$ ). Le tri par insertion sur des données quelconques n'est donc pas « entre le linéaire et le quadratique » : il est quadratique, avec un coefficient deux fois plus petit. Un facteur constant ne change pas la loi — et c'est la première chose que la mesure sur trois tailles permet de trancher.

Énoncé

Corrigé