Algorithmes de tri

En clair. Tris par insertion, sélection et fusion en Python : principes, invariants, terminaison, complexités comparées et méthode d'analyse.

Ce qu'on te demande au bac (Spé NSI) : maîtriser le vocabulaire de « Algorithmes de tri », savoir refaire les raisonnements du cours et les réutiliser sur un sujet ou un document nouveau.

Conseil de révision. Lis d'abord cet encadré, puis fais le quiz : si tu bloques, reprends la partie du cours correspondante.

1. Pourquoi trier ?

Trier un tableau, c'est le réorganiser selon un ordre total (croissant le plus souvent). Un tableau trié permet la recherche dichotomique en $O(\log n)$, la détection de doublons, le calcul de médiane, la fusion de listes. C'est le cas d'étude central de la NSI pour la preuve de terminaison, la correction par invariant et le coût d'un algorithme.

2. Tri par insertion

Principe : on maintient un préfixe trié et on insère chaque nouvel élément à sa place en décalant les plus grands.

def tri_insertion(t):
    for i in range(1, len(t)):
        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
    return t

• Invariant de boucle : au début de l'itération $i$, t[0:i] contient les mêmes éléments qu'au départ, triés.
• Terminaison : i croît strictement jusqu'à len(t) ; la boucle interne décroît j.
• Coût : $O(n^2)$ dans le pire cas (tableau décroissant), $O(n)$ si le tableau est déjà trié — d'où son intérêt sur les petites données presque triées.

3. Tri par sélection

Principe : chercher le minimum du reste du tableau et l'échanger avec la première case non triée.

def tri_selection(t):
    for i in range(len(t)):
        imin = i
        for j in range(i + 1, len(t)):
            if t[j] < t[imin]:
                imin = j
        t[i], t[imin] = t[imin], t[i]
    return t

• Invariant : t[0:i] contient les i plus petits éléments, triés et définitivement placés.
• Coût : toujours $\dfrac{n(n-1)}{2}$ comparaisons, soit $O(n^2)$, mais seulement $n-1$ échanges.

4. Tri fusion (approche « diviser pour régner »)

def fusion(a, b):
    r, i, j = [], 0, 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            r.append(a[i]); i += 1
        else:
            r.append(b[j]); j += 1
    return r + a[i:] + b[j:]

def tri_fusion(t):
    if len(t) <= 1:
        return t
    m = len(t) // 2
    return fusion(tri_fusion(t[:m]), tri_fusion(t[m:]))

Coût $O(n\log n)$ : $\log_2 n$ niveaux de découpage, $O(n)$ de fusion par niveau. Il nécessite un espace mémoire supplémentaire $O(n)$.

5. Comparaison chiffrée

Ordre de grandeur : pour $n = 10^6$, $n^2 = 10^{12}$ opérations (des heures) contre $n\log_2 n \approx 2\times10^7$ (une fraction de seconde). C'est l'argument décisif en faveur du tri fusion sur de grands volumes.

6. Méthode d'analyse attendue à l'épreuve

1. Décrire le principe en une phrase.
2. Donner un invariant de boucle et l'utiliser pour justifier la correction.
3. Justifier la terminaison (variant : quantité entière positive strictement décroissante).
4. Compter les comparaisons pour établir la complexité.

7. Erreurs fréquentes

• Décaler les éléments dans le mauvais sens et écraser une valeur (tri par insertion).
• Oublier le cas de base de la récursion dans le tri fusion.
• Confondre « stable » (ordre des égaux préservé) et « en place » (mémoire $O(1)$).
• Annoncer $O(n\log n)$ pour un tri quadratique.

À retenir

• Insertion et sélection : simples, en place, $O(n^2)$.
• Fusion : récursif, $O(n\log n)$, mémoire supplémentaire.
• Toute analyse rigoureuse combine invariant, variant et coût.