Parcours séquentiel et tris

Le parcours séquentiel

Un parcours séquentiel consiste à examiner les éléments d'un tableau un par un, de l'indice 0 à l'indice len(t) - 1, en mettant à jour une ou plusieurs variables au fil du parcours.

def somme(t):

    s = 0

    for x in t:

        s = s + x

    return s

La moyenne s'en déduit : somme(t) / len(t). Le tableau doit être non vide (c'est une précondition), sinon on divise par zéro.

Pour compter les occurrences d'une valeur x, on utilise un compteur :

def occurrences(t, x):

    c = 0

    for e in t:

        if e == x:

            c = c + 1

    return c

Le coût est linéaire : pour un tableau de $n$ éléments, on effectue environ $n$ opérations. Si $n$ est multiplié par 10, le temps est multiplié par 10 environ.

Pour rechercher une occurrence, on s'arrête dès qu'on la trouve, avec un return anticipé :

def position(t, x):

    for i in range(len(t)):

        if t[i] == x:

            return i

    return -1

Par exemple, position([4, 9, 2, 9, 7], 2) renvoie 2 et position([4, 9, 2, 9, 7], 5) renvoie -1. Dans le pire cas (valeur absente), on parcourt tout le tableau : le coût reste linéaire.

Pour renvoyer tous les indices du maximum en un seul parcours, on garde la liste des indices du maximum courant : si on trouve un élément strictement plus grand, on repart d'une liste [i] ; s'il est égal, on ajoute i.

La recherche d'un extremum (ou de tous les indices de l'extremum) effectue $n-1$ comparaisons : le coût est linéaire. La terminaison est évidente : la boucle for est bornée, elle parcourt au plus $n$ éléments puis s'arrête.

Le tri par sélection

Idée : on cherche le plus petit élément du tableau et on le place en position 0 ; puis le plus petit du reste, placé en position 1 ; et ainsi de suite.

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]

À chaque tour de la boucle externe, m est l'indice du minimum de t[i..n-1], puis on échange t[i] et t[m].

Coût

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

Ce nombre ne dépend pas de l'ordre initial des éléments. Il est de l'ordre de $n^2$ : le coût est quadratique. Si $n$ est multiplié par 10, le nombre de comparaisons est multiplié par 100 environ.

Le tri par insertion

Idée : comme quand on range ses cartes en main. Le début du tableau est déjà trié ; on prend l'élément suivant et on l'insère à sa place en décalant vers la droite les éléments plus grands.

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

• Tableau déjà trié : le while s'arrête immédiatement à chaque tour, soit environ $n-1$ comparaisons : coût linéaire.

• Tableau trié en ordre décroissant (pire cas) : l'élément d'indice $i$ est décalé $i$ fois, soit $1 + 2 + \dots + (n-1) = \dfrac{n(n-1)}{2}$ déplacements : coût quadratique.

Un tri est stable s'il conserve l'ordre relatif des éléments de même clé. C'est utile pour trier des couples (nom, note) par note : à note égale, l'ordre alphabétique précédent est conservé.

Invariant, variant et correction

Tester un programme 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 à tout élément de t[i..n-1].

• Initialisation : pour $i=0$, la partie t[0..-1] est vide, la propriété est vraie.

• Conservation : on place en t[i] le minimum de t[i..n-1] ; il est supérieur ou égal aux éléments de t[0..i-1] et inférieur ou égal à ceux de t[i+1..n-1]. La propriété est vraie au tour $i+1$.

• Conclusion : au début du tour $i = n-1$ (c'est-à-dire à la sortie de la boucle), l'invariant donne t[0..n-2] trié et ses éléments inférieurs ou égaux à t[n-1] : tout le tableau est trié.

Terminaison. La boucle for est bornée : elle se termine toujours.

Tri par insertion. Invariant du for, au début du tour $i$ : t[0..i-1] contient les éléments initiaux de t[0..i-1], triés. Variant du while : $j$, entier naturel qui diminue strictement de 1 à chaque tour ; la boucle s'arrête dès que $j=0$ ou que t[j-1] <= v. Dans les deux cas, la terminaison est garantie : $j$ est un entier supérieur ou égal à 0 qui diminue strictement à chaque tour, donc il ne peut pas diminuer indéfiniment.

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

Pour revenir au classement de 10 000 scores : le maximum se trouve en un parcours (10 000 opérations), la moyenne aussi ; un tri quadratique en demande de l'ordre de 50 millions. Et un invariant garantit que le tri est juste.

L'essentiel

• Un parcours séquentiel examine chaque élément une fois : maximum, occurrences, moyenne. Coût linéaire. On initialise le maximum avec t[0].

• Tri par sélection : on place le minimum du reste en position $i$ ; $\frac{n(n-1)}{2}$ comparaisons, quel que soit le tableau ; coût quadratique.

• Tri par insertion : on insère t[i] dans la partie déjà triée ; linéaire sur un tableau trié, quadratique dans le pire cas (ordre décroissant).

• Un invariant prouve la correction, un variant prouve la terminaison.

• Un jeu de tests réussi ne prouve pas la correction d'un programme.