Parcours séquentiel d'un tableau et tris

Le parcours séquentiel

Un parcours séquentiel consiste à examiner les éléments d'un tableau un par un, dans l'ordre des indices, de t[0] à t[n-1]. On l'écrit avec une boucle for.

Trois problèmes classiques se résolvent ainsi : la recherche d'une occurrence, la recherche d'un extremum (maximum ou minimum) et le calcul d'une moyenne.

L'idée du maximum : on garde en mémoire le meilleur candidat provisoire m, qu'on met à jour dès qu'on rencontre un élément plus grand. À la fin du parcours, m est le maximum de tout le tableau.

La recherche d'occurrences suit le même schéma avec un compteur : on l'incrémente à chaque fois que t[i] == x.

Le tri par sélection

Pour classer les temps de Lucas, une idée naturelle : chercher le plus petit, le placer en première position, puis recommencer sur le reste.

def tri_selection(t):

    n = len(t)

    for i in range(n - 1):

        m = i

        for j in range(i + 1, n):

            if t[j] < t[m]:

                m = j

        t[i], t[m] = t[m], t[i]

Coût. À l'étape $i$, la boucle interne fait $n-1-i$ comparaisons. Au total :

Ce nombre ne dépend pas du contenu du tableau. Il est de l'ordre de $n^2$ : le coût est quadratique. Multiplier $n$ par 10 multiplie le nombre de comparaisons par environ 100.

Le tri par insertion

Quand tu ranges des cartes dans ta main, tu prends la carte suivante et tu la glisses à sa place parmi celles déjà triées. C'est le tri par insertion.

def tri_insertion(t):

    for i in range(1, len(t)):

        v = t[i]

        j = i

        while j > 0 and t[j - 1] > v:

            t[j] = t[j - 1]

            j = j - 1

        t[j] = v

Coût. Dans le pire cas (tableau trié en ordre décroissant), chaque élément traverse tout le début du tableau : $1 + 2 + \dots + (n-1) = \frac{n(n-1)}{2}$ décalages, donc un coût quadratique. Dans le meilleur cas (tableau déjà trié), la condition t[j-1] > v est fausse tout de suite : $n-1$ comparaisons seulement, un coût linéaire.

Invariant, variant : prouver qu'un algorithme est correct

Tester un programme sur quelques exemples ne prouve pas qu'il est correct. Pour le prouver, on utilise deux outils.

Tri par sélection. Invariant de la boucle externe, au début du tour $i$ : « t[0..i-1] est trié, et chacun de ses éléments est inférieur ou égal à tous ceux de t[i..n-1] ».

• Initialisation : pour $i = 0$, la partie t[0..-1] est vide, l'invariant est vrai.

• Conservation : on choisit le minimum de t[i..n-1] et on le met en position $i$. Il est supérieur ou égal à ceux de t[0..i-1] grâce à l'invariant (ceux-ci sont inférieurs ou égaux à tous les éléments de t[i..n-1]), et il est inférieur ou égal aux autres éléments de t[i..n-1] par définition du minimum : l'invariant est vrai pour $i+1$.

• Conclusion : la boucle for i in range(n - 1) se termine après le tour $i = n-2$ ; l'invariant est donc vrai pour $i = n-1$ (valeur de $i$ à la sortie). Il donne t[0..n-2] trié, avec tous ses éléments inférieurs ou égaux à t[n-1] ; le tableau t[0..n-1] est donc trié.

Terminaison. Les boucles for sur un range sont bornées : elles se terminent.

Tri par insertion. Invariant de la boucle for, au début du tour $i$ : « t[0..i-1] contient les éléments initiaux de t[0..i-1], triés ». Variant de la boucle while : j. Au départ, j = i ≥ 1 est un entier naturel. On n'entre dans le corps de la boucle que si j > 0, et ce corps fait j = j - 1 : j reste donc un entier positif ou nul et diminue strictement (de 1) à chaque tour. Une suite d'entiers naturels strictement décroissante ne peut pas être infinie : après au plus $i$ tours, j vaut 0, la condition j > 0 est fausse et la boucle s'arrête (elle peut aussi s'arrêter avant, si t[j - 1] > v devient faux). La boucle while se termine donc toujours.

Nombre maximal de décalages. Au tour $i$, au plus $i$ décalages. Le total maximal est $\frac{n(n-1)}{2}$, atteint pour un tableau trié en ordre décroissant (tous les éléments sont distincts).

Stabilité. Un tri est stable s'il conserve l'ordre relatif des éléments égaux. Le tri par insertion avec la condition t[j-1] > v (inégalité stricte) est stable : un élément égal à v n'est pas décalé. Avec >=, v passerait devant ses égaux : la stabilité serait perdue.

def tri_selection(t):

    n = len(t)

    for i in range(n - 1):

        m = i

        for j in range(i + 1, n):

            if t[j] < t[m]:

                m = j

        t[i], t[m] = t[m], t[i]

def tri_insertion(t):

    for i in range(1, len(t)):

        v = t[i]

        j = i

        while j > 0 and t[j - 1] > v:

            t[j] = t[j - 1]

            j = j - 1

        t[j] = v

Retour au début : pour trouver le meilleur tour de Lucas, on fait un parcours séquentiel (maximum adapté en minimum) ; pour classer tous ses temps, on trie par sélection ou par insertion, en prouvant la correction avec un invariant.

L'essentiel