Le tri par insertion cherche la place de la carte séquentiellement

Exercice d'entraînement · niveau 2 · NSI (première), chapitre 7 — Parcourir, trier, prouver · Variantes des deux tris

Énoncé

Le tri par insertion cherche la place de la carte séquentiellement. Le tableau de gauche étant trié, on peut la chercher par dichotomie (chapitre 8). Écrire cette variante, et mesurer ce qu'elle gagne — et ce qu'elle ne gagne pas.

Corrigé


def position_insertion(t, x, fin):
    """Indice où insérer x dans la tranche triée t[0..fin-1].

    Précondition  : t[0..fin-1] est croissant.
    Postcondition : tous les t[k] pour k < résultat sont <= x, et tous
                    ceux pour résultat <= k < fin sont > x.
    """
    g, d = 0, fin
    while g < d:
        m = (g + d) // 2
        if t[m] > x:
            d = m
        else:
            g = m + 1
    return g

def tri_insertion_dicho(t):
    """Tri par insertion, position trouvée par dichotomie."""
    for i in range(1, len(t)):
        x = t[i]
        p = position_insertion(t, x, i)
        for k in range(i, p, -1):
            t[k] = t[k - 1]
        t[p] = x

Validation : $2000$ tableaux tirés au hasard — $2000$ cas passent.

La mesure, sur un tableau trié à l'envers — le pire cas.

	insertion	insertion dichotomique
$n$	comparaisons	décalages	comparaisons	décalages
$100$	$4950$	$4950$	$573$	$4950$
$200$	$19900$	$19900$	$1345$	$19900$
$400$	$79800$	$79800$	$3089$	$79800$
$800$	$319600$	$319600$	$6977$	$319600$

Rapports quand $n$ double : $2, 35$ puis $2, 30$ puis $2, 26$ pour les comparaisons dichotomiques — la signature du $n lo g_{2} n$ ; et $4, 02$ , $4, 01$ , $4, 00$ pour les décalages — la signature du quadratique.

Ce qu'elle gagne, et ce qu'elle ne gagne pas. Les comparaisons passent de $319600$ à $6977$ pour $n = 800$ : divisées par $46$ . Mais les décalages ne bougent pas d'une unité. Or c'est bien eux qui dominent : le tri reste quadratique.

La leçon. On a optimisé ce qui n'était pas le goulot. La dichotomie trouve la place plus vite, mais il faut toujours déplacer physiquement tous les éléments qui sont après. Cette variante n'est utile que si comparer coûte beaucoup plus cher que déplacer — comparer de longues chaînes, par exemple. Avant d'optimiser, mesurer laquelle des deux opérations domine.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.