Tris par sélection et par insertion

Introduction

Trier un tableau, c'est en ranger les éléments dans l'ordre croissant (ou décroissant). C'est l'une des opérations les plus utiles en informatique — les annuaires sont triés par nom, les classements par score, les fichiers par date. Au-delà de l'usage direct, un tableau trié ouvre des possibilités : on peut y chercher beaucoup plus vite (vous le verrez au cours suivant avec la dichotomie). Ce cours présente deux tris naïfs mais fondamentaux, le tri par sélection et le tri par insertion, et démontre qu'ils coûtent tous deux $\mathcal{O}(n^2)$.

Le tri par sélection

Idée : à chaque étape, on sélectionne le plus petit élément non encore trié et on le place à sa position définitive.

Plus précisément, on découpe le tableau en deux zones :

• à gauche, une zone triée (au début vide, puis qui grandit) ;
• à droite, une zone non triée (qui rétrécit).

À l'étape $i$, on cherche le minimum dans la zone non triée et on l'échange avec l'élément en position $i$.

def tri_selection(t):
    n = len(t)
    for i in range(n):
        # Cherche l'indice du minimum dans t[i:]
        i_min = i
        for j in range(i + 1, n):
            if t[j] < t[i_min]:
                i_min = j
        # Échange t[i] et t[i_min]
        t[i], t[i_min] = t[i_min], t[i]
    return t

print(tri_selection([5, 2, 8, 1, 9, 3]))
# [1, 2, 3, 5, 8, 9]

Invariant du tri par sélection

Notons l'invariant suivant, vrai à la fin de chaque tour de la boucle externe pour l'indice $i$ :

Après le tour $i$, les cases t[0], …, t[i] contiennent les $i+1$ plus petits éléments du tableau, rangés dans l'ordre croissant.

Quand $i$ atteint $n-1$, l'invariant dit que tout le tableau est trié. C'est ce qu'on voulait.

Terminaison

La boucle externe parcourt range(n) — c'est un for sur un intervalle fini. Elle s'arrête donc forcément après exactement $n$ tours. La boucle interne aussi (range(i+1, n)). L'algorithme termine toujours.

Le tri par insertion

Idée : à chaque étape, on insère l'élément courant à sa place correcte dans la portion déjà triée à gauche.

C'est exactement comme on trie une main de cartes en la prenant carte par carte :

• la première carte forme une « main triée » de taille 1 ;
• on prend la 2ᵉ carte et on l'insère à gauche ou à droite de la 1ʳᵉ ;
• on prend la 3ᵉ et on l'insère parmi les 2 déjà triées ;
• etc.

def tri_insertion(t):
    n = len(t)
    for i in range(1, n):
        # On veut insérer t[i] dans t[0..i-1] (déjà trié)
        valeur = t[i]
        j = i - 1
        # On décale vers la droite tant qu'on trouve plus grand
        while j >= 0 and t[j] > valeur:
            t[j + 1] = t[j]
            j -= 1
        t[j + 1] = valeur
    return t

print(tri_insertion([5, 2, 8, 1, 9, 3]))
# [1, 2, 3, 5, 8, 9]

Invariant du tri par insertion

Au début du tour pour l'indice $i$, la portion t[0..i-1] contient les mêmes éléments qu'au départ — mais triés dans l'ordre croissant.

Au début ($i = 1$), t[0..0] ne contient qu'un élément, donc trivialement trié. À chaque tour, on insère t[i] à la bonne place et la portion triée s'agrandit d'un élément. Quand $i$ vaut $n$, tout le tableau est trié.

Terminaison

Boucle externe : for sur range(1, n) — fini. Boucle interne : un while qui décrémente j à chaque tour, et qui s'arrête au plus tard quand j devient négatif. Donc terminaison garantie.

Comparaison de coût

Pour un tableau de taille $n$, comptons les comparaisons :

Tri par sélection : pour chaque $i$ de 0 à $n-1$, on parcourt les $n - i - 1$ éléments suivants. Total :

C'est en $\mathcal{O}(n^2)$, quel que soit le contenu du tableau (déjà trié ou non, peu importe).

Tri par insertion : dans le pire des cas (tableau trié en sens inverse), chaque insertion remonte jusqu'au début — soit $1 + 2 + \dots + (n - 1) = \frac{n(n-1)}{2}$ comparaisons. C'est aussi en $\mathcal{O}(n^2)$. En revanche, dans le meilleur des cas (tableau déjà trié), chaque tour ne fait qu'une seule comparaison qui échoue immédiatement — total $n - 1$ et coût $\mathcal{O}(n)$.

Pièges courants

• Confondre les deux : la sélection cherche un minimum puis échange, l'insertion décale des éléments puis pose.
• Oublier la terminaison du while dans le tri par insertion : j >= 0 est essentiel — sinon t[-1] lit la fin du tableau (bug subtil en Python).
• Croire qu'un tri en $\mathcal{O}(n^2)$ est inutilisable : pour $n \leq 100$, c'est très bien. Pour $n = 10^6$, c'est rédhibitoire.

Pour aller plus loin

Il existe des tris bien plus rapides — tri fusion, tri rapide, tri par tas — tous en $\mathcal{O}(n \log n)$. Vous les rencontrerez en Terminale. Pour l'instant, retenez que trier coûte cher — d'où l'intérêt d'avoir une recherche efficace dans un tableau déjà trié, ce qui amène au cours suivant.