Parcourir, trier, prouver

Jusqu'ici, on a écrit des programmes et on les a testés. Le chapitre 3 disait déjà pourquoi cela ne suffit pas : « le succès d'un jeu de tests ne garantit pas la correction d'un programme ». Un test porte sur une entrée ; un programme doit être juste sur toutes.

Ce chapitre franchit le pas. On y écrit les algorithmes classiques du programme — parcours, recherche, tris — et surtout on apprend à démontrer qu'ils sont corrects et qu'ils s'arrêtent, à l'aide de deux outils : l'invariant et le variant. C'est le moment où l'informatique cesse d'être une affaire d'essais pour devenir une science.

7.1 Le parcours séquentiel

7.1.1 Rechercher une occurrence

def recherche(t, v):
    """Indice de la PREMIÈRE occurrence de v dans t, ou -1 si v n'y figure pas.

    Précondition  : les éléments de t sont comparables à v par ==.
    Postcondition : si le résultat r vaut -1, aucun élément de t n'est égal
                    à v ; sinon 0 <= r < len(t) et t[r] == v.
    """
    for i in range(len(t)):
        if t[i] == v:
            return i
    return -1

7.1.2 Extrémum et moyenne

def indice_maximum(t):
    """Indice d'un plus grand élément de t.

    Précondition  : t est non vide.
    Postcondition : t[r] >= t[k] pour tout k. En cas d'ex aequo, l'indice
                    du PREMIER maximum rencontré.
    """
    assert len(t) > 0, "tableau vide"
    m = 0
    for i in range(1, len(t)):
        if t[i] > t[m]:
            m = i
    return m


def moyenne(t):
    """Moyenne arithmétique de t. Précondition : t est un tableau non vide
    de nombres. La postcondition est celle du chapitre 3, avec sa tolérance."""
    assert len(t) > 0, "tableau vide"
    total = 0
    for x in t:
        total = total + x
    return total / len(t)

7.2 Prouver qu'une boucle est correcte : l'invariant

La démonstration se fait toujours en trois temps, et il faut les trois :

• Initialisation : l'invariant est vrai avant le premier tour.
• Conservation : s'il est vrai avant un tour, il l'est encore après.
• Terminaison : quand la boucle s'arrête, l'invariant plus la condition d'arrêt donnent le résultat cherché.

L'invariant se voit bien si l'on dessine la frontière qu'il déplace :

Figure : L'invariant de `indice_maximum` au moment où $i=4$. La propriété porte sur la partie déjà parcourue ; on ne prétend rien sur le reste.

7.3 Le tri par sélection

Le principe : chercher le plus petit élément de la partie non triée, et l'amener à sa place définitive.

def tri_selection(t):
    """Trie le tableau t par ordre croissant, SUR PLACE.

    Postcondition : t est croissant et contient exactement les mêmes
                    éléments qu'au départ.
    """
    n = len(t)
    for i in range(n - 1):
        # invariant : t[0..i-1] est trié et contient les i plus petits
        #             éléments du tableau initial
        m = i
        for j in range(i + 1, n):
            if t[j] < t[m]:
                m = j
        t[i], t[m] = t[m], t[i]        # l'échange du chapitre 4

Figure : L'invariant du tri par sélection. La frontière avance d'une case à chaque tour, et ce qui

est à gauche ne bouge plus jamais.</div>

Démonstration (Correction)

Invariant : avant le tour $i$, t[0..i-1] est trié par ordre croissant et contient les $i$ plus petits éléments du tableau, tandis que t[i..n-1] contient les autres.

Initialisation. Pour $i=0$, la partie t[0..-1] est vide : elle est triée et contient les $0$ plus petits éléments. Vrai.

Conservation. La boucle interne calcule l'indice m d'un plus petit élément de t[i..n-1] — c'est l'invariant de la section précédente, appliqué à un sous-tableau. L'échange place cet élément en position $i$. Comme, par hypothèse, tous les éléments de t[0..i-1] sont plus petits que ceux de t[i..n-1], le nouvel élément en position $i$ est supérieur ou égal à tous ceux qui le précèdent : t[0..i] est donc trié et contient les $i+1$ plus petits éléments.

Terminaison. À la sortie, $i=n-1$ : t[0..n-2] est trié et contient les $n-1$ plus petits éléments. Le dernier élément restant est donc le plus grand, et il est déjà à sa place — c'est pourquoi la boucle s'arrête à $n-1$ et non à $n$.

Enfin, la seule opération qui modifie le tableau est un échange : le contenu est donc préservé, ce qui établit la seconde moitié de la postcondition.

Complexité : Coût du tri par sélection

Au tour $i$, la boucle interne effectue $n-1-i$ comparaisons. Le total vaut

$$\sum _{i=0}^{n-2}(n-1-i)=(n-1)+(n-2)+\cdots +1=\frac{n(n-1)}{2}.$$

Le coût est quadratique : il croît comme le carré de la taille. Doubler le tableau multiplie le travail par quatre.

Ce nombre ne dépend pas du contenu : un tableau déjà trié coûte exactement autant qu'un tableau en désordre. Le tri par sélection n'a ni meilleur ni pire cas.

7.4 Le tri par insertion

Le principe est celui du joueur de cartes : prendre les cartes une à une et insérer chacune à sa place parmi celles déjà en main.

def tri_insertion(t):
    """Trie le tableau t par ordre croissant, SUR PLACE.

    Postcondition : t est croissant et contient exactement les mêmes
                    éléments qu'au départ.
    """
    for i in range(1, len(t)):
        # invariant : t[0..i-1] est trié
        x = t[i]                       # la carte que l'on insère
        j = i
        while j > 0 and t[j - 1] > x:  # variant : j décroît strictement
            t[j] = t[j - 1]            # on décale vers la droite
            j = j - 1
        t[j] = x

Figure : Le tri par insertion, comme on range des cartes en main. Sur un tableau déjà trié, la

carte s'arrête tout de suite : c'est pourquoi ce tri devient linéaire dans son meilleur cas.</div>

Démonstration (Correction)

Invariant : avant le tour $i$, t[0..i-1] est trié et contient les mêmes éléments que les $i$ premiers du tableau initial.

Initialisation. Pour $i=1$, t[0..0] n'a qu'un élément : il est trié.

Conservation. La boucle interne décale vers la droite tous les éléments de t[0..i-1] strictement supérieurs à x, puis dépose x dans le trou. Les éléments décalés restent dans le même ordre relatif, ceux qui précèdent x lui sont inférieurs ou égaux, ceux qui le suivent lui sont supérieurs : t[0..i] est donc trié, et contient les mêmes éléments qu'avant plus x.

Terminaison. À la sortie, $i=n$ : t[0..n-1] est trié. C'est la postcondition.

7.4.1 La terminaison ne va plus de soi

Important

Le tri par sélection n'emploie que des boucles for : elles font un nombre de tours connu d'avance, donc elles s'arrêtent — c'est acquis depuis le chapitre 3. Le tri par insertion contient une boucle while : rien ne garantit a priori qu'elle s'arrête. Il faut le prouver.

Définition 7.3Variant de boucle

Un variant de boucle est une quantité entière, positive ou nulle, qui décroît strictement à chaque tour. Une telle quantité ne peut pas décroître indéfiniment en restant positive : la boucle s'arrête donc nécessairement, après un nombre fini de tours.

Démonstration (Terminaison de la boucle interne)

Prenons la variable j comme variant.

Elle est entière et positive : la condition j > 0 garantit qu'on n'entre dans le corps que si j $\ge 1$, et le corps la ramène à j $\ge 0$.

Elle décroît strictement : le corps exécute j = j - 1, sans aucune autre affectation à j.

Une suite d'entiers positifs strictement décroissante est finie : la boucle s'arrête en au plus $i$ tours.

AttentionL'ordre des deux tests n'est pas indifférent

La condition s'écrit while j > 0 and t[j - 1] > x — dans cet ordre. Inversée, elle évaluerait t[j - 1] avec j valant $0$, donc t[-1] : en Python, le dernier élément du tableau, ce qui ne provoque aucune erreur mais compare n'importe quoi. C'est l'évaluation en court-circuit du chapitre 2, et c'est ici qu'elle protège la correction de l'algorithme.

Complexité : Coût du tri par insertion

Contrairement au tri par sélection, il dépend du contenu.

Meilleur cas — tableau déjà trié. La condition t[j-1] > x est fausse d'emblée à chaque tour : une seule comparaison par élément, soit $n-1$ au total. Le coût est linéaire.

Pire cas — tableau trié à l'envers. Chaque élément doit remonter jusqu'au début : $1+2+\cdots +(n-1)=\frac{n(n-1)}{2}$ comparaisons. Le coût est quadratique, comme le tri par sélection.

iRemarqueLequel choisir ?

Les deux sont quadratiques dans le pire cas, et le programme n'en demande pas davantage. Une différence mérite pourtant d'être connue : sur des données presque triées — le cas fréquent en pratique — le tri par insertion est très rapide, alors que le tri par sélection paie toujours le plein tarif. C'est pour cette raison qu'il sert encore, à l'intérieur d'algorithmes de tri plus élaborés, sur les petits sous-tableaux.

Repère historique : La preuve avant la machine

L'idée qu'un programme se démontre plutôt qu'il ne s'essaie est aussi ancienne que l'informatique elle-même : elle apparaît dès la fin des années 1940 chez Alan Turing, et elle est formalisée en 1969 par Tony Hoare, qui propose une logique où l'on écrit $\{P\}C\{Q\}$ — « si $P$ est vraie avant l'exécution de $C$, alors $Q$ est vraie après ». Vos préconditions et postconditions du chapitre 3 sont exactement ce $P$ et ce $Q$ ; les invariants de ce chapitre sont ce qui permet de franchir une boucle.

Hoare est aussi l'auteur, en 1961, du tri rapide (quicksort) — dont l'étude viendra plus tard. Un même chercheur aura donc donné à la fois un algorithme célèbre et le moyen de prouver qu'un algorithme est juste.

7.5 Mesurer plutôt que croire

def tri_selection_compte(t):
    """Comme tri_selection, mais renvoie le nombre de comparaisons."""
    n = len(t)
    comparaisons = 0
    for i in range(n - 1):
        m = i
        for j in range(i + 1, n):
            comparaisons = comparaisons + 1
            if t[j] < t[m]:
                m = j
        t[i], t[m] = t[m], t[i]
    return comparaisons

Exemple 7.4Ce que donne la mesure

	Sélection	Insertion
$n$	tous les cas	trié	aléatoire	trié à l'envers
10	45	9	30	45
100	4 950	99	2 565	4 950
200	19 900	199	10 144	19 900

Les colonnes « trié » et « trié à l'envers » sont exactes ; la colonne « aléatoire » est une moyenne sur 400 tirages, et elle vaut environ la moitié du pire cas — ce qui se comprend : en moyenne, un élément doit remonter la moitié de la partie déjà triée.

Deux enseignements. La colonne « sélection » ne bouge jamais, et vaut exactement $n(n-1)/2$ — $4950$ pour $n=100$. Et quand $n$ double, de 100 à 200, ce nombre est multiplié par quatre : c'est cela, un coût quadratique. La colonne « trié » du tri par insertion, elle, ne fait que doubler.

Figure : Les trois coûts rencontrés dans ce livre, à $n=100$ : 7 comparaisons pour la

recherche dichotomique, 100 pour le parcours séquentiel, 4 950 pour le tri par sélection. Il faut deux cadrans parce qu'aucune échelle unique ne les montre tous : à gauche le quadratique écrase les deux autres, à droite l'agrandissement sépare enfin le linéaire du logarithmique.</div>

Piste de projet : Un banc d'essai de tris

Écrire un programme qui compare expérimentalement les deux tris : nombre de comparaisons et durée, sur des tableaux triés, aléatoires et inversés, pour des tailles croissantes. Tracer les courbes, et vérifier que celle du tri par sélection suit bien $n(n-1)/2$.

L'exigence intéressante n'est pas de coder les tris — c'est fait — mais de construire un protocole honnête : plusieurs tirages par taille, tableaux identiques pour les deux algorithmes, et un compte rendu qui distingue ce qui a été mesuré de ce qui a été prédit.

Continuer sur Adloun : animation, QCM, fiches, exercices