Parcours séquentiel d'un tableau

Introduction

La plupart des algorithmes que vous écrirez cette année commencent par la même chose : un parcours séquentiel d'un tableau. On lit les éléments les uns après les autres, du premier au dernier, et on accumule au passage une information — un compteur, une somme, un maximum, ou la confirmation qu'une valeur cherchée est bien présente. C'est l'opération la plus naturelle qu'on puisse faire sur une suite de données, et c'est aussi celle qui sert de mètre étalon pour mesurer le coût des algorithmes plus astucieux que nous verrons ensuite. [PH03]

Le cœur du concept

Un parcours séquentiel d'un tableau t est une boucle qui visite chaque case t[0], t[1], …, t[n-1] exactement une fois, dans l'ordre des indices croissants. En Python, deux écritures sont équivalentes :

# Version 1 : on parcourt les indices
for i in range(len(t)):
    print(t[i])

# Version 2 : on parcourt directement les valeurs
for valeur in t:
    print(valeur)

La version 2 est plus lisible quand on n'a pas besoin de l'indice. La version 1 est préférée quand l'indice lui-même sert (par exemple pour comparer t[i] avec t[i+1]).

Recherche d'une occurrence

Premier usage classique : chercher si une valeur cible est présente dans un tableau (recherche dite linéaire ou séquentielle).

Deux choses à remarquer :

1. Sortie anticipée — dès qu'on trouve, on s'arrête avec return True. Pas besoin de continuer à parcourir.
2. Cas de l'absence — si la boucle finit sans rien trouver, on retourne False. C'est la seule façon de conclure à l'absence : avoir tout vu.

Extremum : trouver le maximum

Deuxième usage : trouver la plus grande valeur. On garde dans une variable maximum la plus grande valeur vue jusqu'ici, qu'on met à jour à chaque case visitée plus grande.

def maximum(tableau):
    """Retourne le plus grand élément de tableau (non vide)."""
    maxi = tableau[0]
    for valeur in tableau[1:]:
        if valeur > maxi:
            maxi = valeur
    return maxi

print(maximum([3, 7, 2, 9, 5]))   # 9

Moyenne arithmétique

Troisième usage : sommer puis diviser.

def moyenne(tableau):
    """Moyenne arithmétique d'un tableau non vide de nombres."""
    somme = 0
    for valeur in tableau:
        somme += valeur
    return somme / len(tableau)

print(moyenne([4, 8, 6, 10]))   # 7.0

Notez qu'on a écrit somme / len(tableau) et non somme / len(somme) — piège fréquent en début d'année.

L'idée d'invariant de boucle

Quand on analyse une boucle, il est utile de pouvoir affirmer qu'une certaine propriété reste vraie d'un tour à l'autre. C'est ce qu'on appelle un invariant de boucle.

Reprenons maximum. À chaque tour, la variable maxi contient la plus grande valeur parmi celles déjà parcourues. C'est vrai :

• avant le premier tour : maxi = tableau[0], et tableau[0] est bien la plus grande valeur parmi {tableau[0]} ;
• à la fin de chaque tour : si la nouvelle valeur est plus grande, on l'a affectée à maxi ; sinon, on garde l'ancienne — donc le max reste celui des valeurs vues, qui inclut maintenant la nouvelle.

Quand la boucle s'arrête, on a parcouru tout le tableau, donc maxi est le maximum… de tout le tableau. C'est ce qu'on voulait démontrer.

Coût du parcours

Un parcours séquentiel d'un tableau de taille $n$ effectue un nombre d'opérations proportionnel à $n$. Si vous doublez la taille du tableau, le temps d'exécution double aussi. On parle d'un coût linéaire, qu'on notera $\mathcal{O}(n)$ dès le prochain cours.

Pièges courants

• Confondre la valeur et l'indice — for v in t donne la valeur, for i in range(len(t)) donne l'indice.
• Dépasser le tableau — t[len(t)] n'existe jamais, les indices vont de 0 à len(t) - 1.
• Oublier le cas vide — un tableau vide n'a ni minimum ni maximum ; il faut décider quoi faire (exception, valeur sentinelle, etc.).

Pour aller plus loin

Le parcours séquentiel est partout. Mais quand on cherche une valeur dans un tableau trié, on peut faire bien mieux qu'un parcours linéaire — c'est l'objet du cours 4 sur la recherche dichotomique. Avant cela, on passe au cours 2 pour poser proprement la notion de coût d'un algorithme.