💻 NSI (spécialité)1ereCours

Algorithmes sur les tableaux : parcours et tris

Voir la fiche de révision →Tous les chapitres

📖

Cours

Algorithmes sur les tableaux : parcours et tris

Un algorithme est une méthode précise pour résoudre un problème, indépendante du langage.

Ce chapitre étudie les algorithmes les plus courants sur les tableaux : le parcours séquentiel (rechercher une valeur, un maximum, calculer une moyenne), puis deux algorithmes de tri, par sélection et par insertion.

Au-delà du code, on apprend trois choses : prouver qu'un algorithme est correct avec un invariant de boucle, justifier sa terminaison, et évaluer son coût.

1. Le parcours séquentiel

1.1 Rechercher une occurrence

On veut savoir si une valeur v est dans un tableau t.

On compare v à chaque case, de gauche à droite, et on s'arrête dès qu'on la trouve.

def recherche(t, v):
    """Renvoie l'index de la première occurrence de v dans t, ou -1 si v est absent."""
    for i in range(len(t)):
        if t[i] == v:
            return i
    return -1

prenoms = ["Lina", "Hugo", "Aïcha", "Tom", "Hugo"]
print(recherche(prenoms, "Hugo"))
print(recherche(prenoms, "Zoé"))

La méthode fonctionne pour des valeurs de type quelconque : nombres, chaînes, p-uplets.

1.2 Extremum et moyenne

def maximum(t):
    """Renvoie le plus grand élément de t (t non vide)."""
    m = t[0]
    for i in range(1, len(t)):
        if t[i] > m:
            m = t[i]
    return m

def moyenne(t):
    """Renvoie la moyenne des éléments de t (t non vide)."""
    total = 0
    for x in t:
        total = total + x
    return total / len(t)

temperatures = [-4, -9, -1, -6]
print(maximum(temperatures))
print(moyenne(temperatures))

def index_maximum(t):
    i_max = 0
    # à toi
    return i_max

1.3 Coût linéaire

Pour la recherche, le pire cas est la valeur absente, ou placée en dernière position : il faut $n$ comparaisons.

Pour le maximum et la moyenne, il faut $n - 1$ ou $n$ opérations.

Comptons les comparaisons dans le pire cas, pour trois tailles de tableau.

def recherche_comptee(t, v):
    """Comme recherche, mais renvoie le nombre de comparaisons effectuées."""
    comparaisons = 0
    for i in range(len(t)):
        comparaisons = comparaisons + 1
        if t[i] == v:
            return comparaisons
    return comparaisons

for n in [100, 1000, 10000]:
    t = [0] * n
    print(n, "cases :", recherche_comptee(t, 1), "comparaisons")

2. Le tri par sélection

2.1 L'idée

Trier, c'est réordonner les éléments par ordre croissant.

Le tri par sélection construit la partie triée par la gauche.

Le programme affiche le tableau après chaque étape. Essaie avec d'autres tableaux.

def tri_selection(t):
    """Trie le tableau t en place, par ordre croissant."""
    n = len(t)
    for i in range(n - 1):
        i_min = i
        for j in range(i + 1, n):
            if t[j] < t[i_min]:
                i_min = j
        t[i], t[i_min] = t[i_min], t[i]
        print("étape", i, ":", t)

tri_selection([5, 2, 9, 1, 7, 3])

À l'étape $0$ , le minimum $1$ est échangé avec $5$ . À l'étape $1$ , le minimum $2$ est déjà en place : rien ne bouge.

2.2 Invariant et correction

La preuve se rédige toujours en trois temps.

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

Conservation. Supposons la propriété vraie au début de l'étape $i$ .

On place en t[i] le minimum de t[i..n-1].

Par l'invariant, il est supérieur ou égal à tous les éléments de t[0..i-1]. Par construction, il est inférieur ou égal à tous ceux de t[i+1..n-1].

Donc t[0..i] est trié et inférieur ou égal au reste : la propriété est vraie au début de l'étape $i + 1$ .

Conclusion. À la sortie de la boucle, t[0..n-2] est trié et inférieur ou égal à t[n-1] : le tableau entier est trié. L'algorithme est correct.

2.3 Terminaison et coût

Terminaison. Les deux boucles for sont bornées : le nombre de tours est fini, l'algorithme s'arrête toujours.

Coût. À l'étape $i$ , la recherche du minimum fait $n - 1 - i$ comparaisons.

Au total : $(n - 1) + (n - 2) + \cdots + 1 = \dfrac{n(n - 1)}{2}$ comparaisons, quel que soit l'état initial du tableau.

def tri_selection(t):
    n = len(t)
    for i in range(n - 1):
        i_min = i
        # à toi : cherche l'index du minimum de t[i..n-1]
        t[i], t[i_min] = t[i_min], t[i]
    return t

3. Le tri par insertion

3.1 L'idée

C'est la méthode du joueur de cartes.

def tri_insertion(t):
    """Trie le tableau t en place, par ordre croissant."""
    n = len(t)
    for i in range(1, n):
        x = t[i]
        j = i - 1
        while j >= 0 and t[j] > x:
            t[j + 1] = t[j]
            j = j - 1
        t[j + 1] = x
        print("on insère", x, ":", t)

tri_insertion([5, 2, 9, 1, 7, 3])

Pour insérer $9$ , il n'y a rien à décaler. Pour insérer $1$ , il faut trois décalages.

3.2 Invariant et correction

Initialisation. Pour $i = 1$ , t[0..0] contient un seul élément : il est trié.

Conservation. La boucle while décale vers la droite les éléments de t[0..i-1] supérieurs à $x$ , qui restent dans le même ordre.

Elle place ensuite $x$ juste après le dernier élément inférieur ou égal à $x$ .

Donc t[0..i] est trié et contient les mêmes éléments.

Conclusion. À la fin, t[0..n-1] est trié.

3.3 Terminaison et coût

Terminaison. La boucle for est bornée. Dans la boucle while, j diminue de $1$ à chaque tour et la boucle s'arrête au plus tard quand j vaut $-1$ : j est un variant.

Coût. Cette fois, il dépend du tableau.

Tableau de départ	Comparaisons	Coût
déjà trié (meilleur cas)	une par étape : $n - 1$	linéaire
trié à l'envers (pire cas)	$1 + 2 + \cdots + (n-1) = \dfrac{n(n-1)}{2}$	quadratique
quelconque (en moyenne)	environ la moitié du pire cas	quadratique

Vérifions-le en comptant les comparaisons sur $200$ éléments.

def comparaisons_insertion(t):
    """Trie t par insertion et renvoie le nombre de comparaisons t[j] > x."""
    c = 0
    for i in range(1, len(t)):
        x = t[i]
        j = i - 1
        while j >= 0:
            c = c + 1
            if t[j] <= x:
                break
            t[j + 1] = t[j]
            j = j - 1
        t[j + 1] = x
    return c

n = 200
print("déjà trié        :", comparaisons_insertion(list(range(n))))
print("trié à l'envers  :", comparaisons_insertion(list(range(n, 0, -1))))
print("n(n-1)/2         :", n * (n - 1) // 2)

3.4 Comparer les deux tris

Tri	Pire cas	Meilleur cas	Écritures	Atout
sélection	$n(n-1)/2$ comparaisons	$n(n-1)/2$ , toujours	au plus $n - 1$ échanges	peu d'écritures
insertion	$n(n-1)/2$ comparaisons	$n - 1$ (déjà trié)	jusqu'à $n(n-1)/2$ décalages	rapide sur un tableau presque trié

Les deux tris sont quadratiques dans le pire cas : ils conviennent pour quelques milliers d'éléments.

Pour des millions d'éléments, on utilise des tris plus rapides, comme le tri fusion vu en terminale, ou la fonction sorted de Python, qui fait environ $n \log_2 n$ opérations.

4. Exemple résolu pas à pas

Commence par la question a, que tu peux faire vérifier.

def compte_sup(t, s):
    n = 0
    # à toi
    return n

Correction · Question a : le coût

Il y a une comparaison par élément, donc $n$ comparaisons : le coût est linéaire.

Correction · Question b

Étape $0$ : le minimum de [4, 8, 1, 6] est $1$ ( $3$ comparaisons). Après l'échange : [1, 8, 4, 6].
Étape $1$ : le minimum de [8, 4, 6] est $4$ ( $2$ comparaisons) : [1, 4, 8, 6].
Étape $2$ : le minimum de [8, 6] est $6$ ( $1$ comparaison) : [1, 4, 6, 8].
Total : $3 + 2 + 1 = 6$ comparaisons, soit $\dfrac{4 \times 3}{2}$ .

Correction · Question c

Insérer $8$ : $1$ comparaison avec $4$ , rien ne bouge.
Insérer $1$ : comparé à $8$ puis à $4$ , soit $2$ comparaisons et $2$ décalages : [1, 4, 8, 6].
Insérer $6$ : comparé à $8$ (décalage), puis à $4$ (arrêt), soit $2$ comparaisons : [1, 4, 6, 8].
Total : $5$ comparaisons contre $6$ . L'insertion profite des parties déjà ordonnées.

Correction · Question d

Invariant : au début de l'étape $i$ , t[0..i-1] est trié.
Terminaison du while : j diminue de $1$ à chaque tour et la boucle s'arrête dès que j < 0.
j est un variant : entier, strictement décroissant, minoré par $-1$ .

À retenir

Révise ce chapitre avec KlarIA

Tuteur qui t'explique pas à pas, quiz pour t'entraîner, flashcards pour mémoriser. Gratuit.

Créer mon compte gratuitement→

Besoin d'aide ?

Pose ta question gratuitement→