Méthodes de tri : sélection, bulles, insertion

Plan de cours

Trois recettes pour ranger un paquet de cartes

Trier un tableau, c'est la grande fresque du programme officiel. Trois méthodes au programme — sélection, bulles, insertion — chacune avec sa propre intuition et son propre invariant. Maîtriser les trois est obligatoire.

Concepts clés

1. Sélection : sélectionner le minimum restant et le placer.
2. Bulles : échanger les voisins mal ordonnés jusqu'à stabilisation.
3. Insertion : insérer chaque élément à sa place dans la zone triée.
4. Tous O(N²) : adaptés aux petits tableaux (ou quasi-triés pour insertion).

Avant de commencer

• Q1. Si je vous donne 10 cartes mélangées, comment les trieriez-vous ?
• Q2. Combien de comparaisons faut-il au minimum pour trier 5 éléments différents ?
• Q3. Connaissez-vous une méthode de tri plus rapide que les trois ci-dessus ?

1. Le contenu du cours

1.1 Analogie : trois façons de trier des cartes en main

Sélection. Vous parcourez toutes les cartes pour trouver la plus petite, vous la mettez en première position. Vous recommencez sur les cartes restantes. Etc.

Bulles. Vous comparez les cartes 2 par 2 et échangez si elles sont dans le mauvais ordre. Vous repassez sur toutes les paires jusqu'à ce qu'aucun échange ne soit nécessaire.

Insertion. Vous prenez les cartes une par une et vous les insérez à leur place dans la zone déjà triée (en décalant celles qui doivent céder).

Les trois trient, mais leur rythme et leur élégance diffèrent.

1.2 Tri par sélection

Principe.

• À l'étape i, on cherche le minimum parmi les éléments restants (de l'indice i à N-1).
• On l'échange avec l'élément en position i.
• On répète pour i = 0, 1, …, N-2.

Invariant. À la fin de l'étape i, les i+1 premiers éléments sont les i+1 plus petits du tableau, triés.

Algorithme

Procédure tri_selection(VAR T : tableau, N : entier)
    Variables : i, j, indice_min : entier
    Début
        Pour i de 1 à N - 1 Faire
            indice_min ← i
            Pour j de i + 1 à N Faire
                Si T[j] < T[indice_min] Alors
                    indice_min ← j
                FinSi
            FinPour
            Si indice_min ≠ i Alors
                echanger(T[i], T[indice_min])
            FinSi
        FinPour
    Fin
FinProcédure

Python

def tri_selection(T):
    n = len(T)
    for i in range(n - 1):
        indice_min = i
        for j in range(i + 1, n):
            if T[j] < T[indice_min]:
                indice_min = j
        if indice_min != i:
            T[i], T[indice_min] = T[indice_min], T[i]

Trace avec T = [5, 2, 8, 1, 9] :

Résultat : [1, 2, 5, 8, 9] ✓

Complexité

• Comparaisons : (N-1) + (N-2) + … + 1 = N(N-1)/2 ≈ N² / 2.
• Échanges : au plus N-1 (un par étape).
• Complexité globale : O(N²).

1.3 Tri à bulles

Principe.

• On parcourt le tableau et compare chaque paire de voisins.
• Si T[i] > T[i+1], on échange.
• À la fin du parcours, le plus grand est en dernière position (il a « bullé » vers la droite).
• On recommence sur les éléments restants jusqu'à plus aucun échange.

Invariant. Après le k-ième parcours, les k plus grands éléments sont à leur place finale.

Algorithme

Procédure tri_bulles(VAR T : tableau, N : entier)
    Variables : i, j : entier, echange : booléen
    Début
        Répéter
            echange ← faux
            Pour j de 1 à N - 1 Faire
                Si T[j] > T[j + 1] Alors
                    echanger(T[j], T[j + 1])
                    echange ← vrai
                FinSi
            FinPour
        Jusqu'à NON echange
    Fin
FinProcédure

Python

def tri_bulles(T):
    n = len(T)
    while True:
        echange = False
        for j in range(n - 1):
            if T[j] > T[j + 1]:
                T[j], T[j + 1] = T[j + 1], T[j]
                echange = True
        if not echange:
            break

Trace avec T = [5, 2, 8, 1, 9] (1er passage) :

Fin du passage : [2, 5, 1, 8, 9]. Le 9 est arrivé à sa place finale. On recommence.

Complexité

• Pire cas (tableau inversé) : N(N-1)/2 comparaisons → O(N²).
• Meilleur cas (tableau déjà trié) : N-1 comparaisons → O(N) (un seul passage sans échange).
• Optimisation : la version avec drapeau echange permet la sortie anticipée, indispensable pour atteindre le meilleur cas O(N).

1.4 Tri par insertion

Principe.

• On considère le tableau divisé en deux zones : gauche triée, droite non triée.
• Au départ, la zone triée contient seulement T[0].
• À chaque étape, on prend l'élément suivant de la zone non triée et on l'insère à sa place dans la zone triée, en décalant les éléments plus grands vers la droite.

Invariant. Après l'étape i, les i+1 premiers éléments sont triés (mais ne sont pas forcément les i+1 plus petits du tableau total).

Algorithme

Procédure tri_insertion(VAR T : tableau, N : entier)
    Variables : i, j : entier, cle : entier
    Début
        Pour i de 2 à N Faire
            cle ← T[i]
            j ← i - 1
            Tant que (j >= 1) ET (T[j] > cle) Faire
                T[j + 1] ← T[j]      { décalage }
                j ← j - 1
            FinTantQue
            T[j + 1] ← cle           { insertion }
        FinPour
    Fin
FinProcédure

Python

def tri_insertion(T):
    n = len(T)
    for i in range(1, n):
        cle = T[i]
        j = i - 1
        while j >= 0 and T[j] > cle:
            T[j + 1] = T[j]
            j = j - 1
        T[j + 1] = cle

Trace avec T = [5, 2, 8, 1, 9] :

Complexité

• Pire cas (tableau inversé) : N(N-1)/2 → O(N²).
• Meilleur cas (tableau déjà trié) : N-1 comparaisons sans aucun décalage → O(N).
• Cas réel : très efficace pour les tableaux quasi-triés (par exemple, vous ajoutez un nouvel élément à un tableau déjà trié).

1.5 Tableau comparatif

* Un tri est stable s'il préserve l'ordre relatif des éléments de même valeur. Sélection : non. Bulles et insertion : oui.

1.6 Trace comparative — T = [3, 1, 2]

2. Exercices pratiques

Niveau Débutant — Type bac courant

def tri_insertion(T):
    for i in range(1, len(T)):
        cle = T[i]
        j = i - 1
        while j >= 0 and T[j] > cle:
            T[j + 1] = T[j]
            j -= 1
        T[j + 1] = cle

def recherche_dicho(T, val):
    deb = 0
    fin = len(T) - 1
    while deb <= fin:
        mil = (deb + fin) // 2
        if T[mil] == val:
            return mil
        elif T[mil] < val:
            deb = mil + 1
        else:
            fin = mil - 1
    return -1

# Programme principal
N = int(input("N = "))
T = []
for i in range(N):
    T.append(int(input(f"T[{i}] = ")))

tri_insertion(T)
print("Tableau trié :", T)

val = int(input("Valeur à chercher : "))
indice = recherche_dicho(T, val)

if indice >= 0:
    print(f"Trouvée à l'indice {indice}")
else:
    print("Absente")

Niveau Intermédiaire — Type bac difficile

import random

def tri_selection_compte(T):
    n = len(T)
    cmp = 0
    echg = 0
    for i in range(n - 1):
        indice_min = i
        for j in range(i + 1, n):
            cmp += 1
            if T[j] < T[indice_min]:
                indice_min = j
        if indice_min != i:
            T[i], T[indice_min] = T[indice_min], T[i]
            echg += 1
    return cmp, echg

def tri_bulles_compte(T):
    n = len(T)
    cmp = 0
    echg = 0
    while True:
        a_echange = False
        for j in range(n - 1):
            cmp += 1
            if T[j] > T[j + 1]:
                T[j], T[j + 1] = T[j + 1], T[j]
                echg += 1
                a_echange = True
        if not a_echange:
            break
    return cmp, echg

def tri_insertion_compte(T):
    n = len(T)
    cmp = 0
    echg = 0
    for i in range(1, n):
        cle = T[i]
        j = i - 1
        while j >= 0:
            cmp += 1
            if T[j] > cle:
                T[j + 1] = T[j]
                echg += 1
                j -= 1
            else:
                break
        T[j + 1] = cle
    return cmp, echg

# Comparaison
random.seed(42)
tableau_aleat = [random.randint(1, 100) for _ in range(10)]
tableau_trie = sorted(tableau_aleat)

for nom, methode in [("Sélection", tri_selection_compte),
                     ("Bulles", tri_bulles_compte),
                     ("Insertion", tri_insertion_compte)]:
    T = tableau_aleat.copy()
    cmp, echg = methode(T)
    print(f"{nom} sur aléatoire : {cmp} comparaisons, {echg} échanges")
    
    T = tableau_trie.copy()
    cmp, echg = methode(T)
    print(f"{nom} sur déjà trié : {cmp} comparaisons, {echg} échanges")

Niveau Avancé — Hors bac (bonus)

def position_insertion(T, deb, fin, cle):
    """Dichotomie : retourne la position où insérer cle dans T[deb..fin] trié."""
    while deb <= fin:
        mil = (deb + fin) // 2
        if T[mil] < cle:
            deb = mil + 1
        else:
            fin = mil - 1
    return deb

def tri_insertion_dicho(T):
    cmp = 0
    for i in range(1, len(T)):
        cle = T[i]
        # On utilise position_insertion qui fait log(i) comparaisons
        pos = position_insertion(T, 0, i - 1, cle)
        # cmp ≈ log2(i) à chaque tour
        cmp += max(1, (i).bit_length())  # approximation
        
        # Décaler T[pos..i-1] vers la droite
        for k in range(i, pos, -1):
            T[k] = T[k - 1]
        T[pos] = cle
    return cmp

import random

random.seed(42)
tableau = [random.randint(1, 1000) for _ in range(100)]

# Classique
T = tableau.copy()
cmp_classique, _ = tri_insertion_compte(T)
print(f"Insertion classique : {cmp_classique} comparaisons")

# Dichotomique
T = tableau.copy()
cmp_dicho = tri_insertion_dicho(T)
print(f"Insertion dichotomique : {cmp_dicho} comparaisons")

⚠️ Erreurs fréquentes au bac

Avant le quiz, mémorisez ces pièges classiques qui font perdre des points :

• Erreur 1. Confondre tri par sélection (cherche le min, le place) et tri à bulles (échange voisins). Mécanismes différents.
• Erreur 2. Échange à 2 lignes au lieu de 3 : T[i] = T[j]; T[j] = T[i] perd la valeur initiale. Utiliser une variable temp ou T[i], T[j] = T[j], T[i] en Python.
• Erreur 3. Oublier la borne n-1-i dans la 2e boucle du tri à bulles optimisé. La passe i n'a plus besoin de comparer les i derniers (déjà triés).
• Erreur 4. Trier sans appliquer en place ni retourner un nouveau tableau. Le tri « se perd ».

3. Quiz de vérification

En résumé

Avant la dernière leçon (4.3 Complexité algorithmique), vous devez :

• ✅ Implémenter les trois tris de tête, en algorithmique et en Python,
• ✅ Tracer chacun sur un petit tableau (5 éléments) sans erreur,
• ✅ Distinguer les invariants : zone triée à gauche (insertion), plus grands à droite (bulles), minimum placé (sélection),
• ✅ Choisir entre les trois selon la situation (déjà trié, peu d'échanges autorisés, etc.).

La prochaine leçon prend du recul : comment mesurer l'efficacité d'un algorithme, et pourquoi le bond O(N²) → O(N log N) → O(log N) change tout pour les grandes données.