Algorithmes de tri 🔍

Trier des données est l'un des problèmes les plus étudiés en informatique. Il existe des dizaines d'algorithmes, chacun avec des forces et faiblesses différentes. Comprendre ces algorithmes, c'est comprendre la complexité algorithmique en pratique.

---

1. Bubble Sort (Tri à bulles) — O(n²) 🫧

Principe : On parcourt le tableau en comparant les éléments adjacents. Si deux éléments sont dans le mauvais ordre, on les échange. Les plus grands éléments "remontent" vers la fin comme des bulles dans un verre.

Exécution pas à pas
pseudo
1/12
1FONCTION tri_bulles(tableau)2    n ← taille(tableau)3    POUR i ALLANT DE 0 À n-1 FAIRE4        POUR j ALLANT DE 0 À n-i-2 FAIRE   ⬅ Les i derniers sont déjà à leur place5            SI tableau[j] > tableau[j+1] ALORS6                échanger(tableau[j], tableau[j+1])  ⬅ Bulle qui remonte7            FIN SI8        FIN POUR9    FIN POUR10    RETOURNER tableau11FIN FONCTION12 
🧩
FONCTION tri_bulles(tableau)
FONCTION tri_bulles(tableau)Le programme exécute cette action, puis passe à la suivante.
On définit une fonction appelée "tri_bulles(tableau)". Cette fonction contient des instructions qui seront exécutées quand on l'appelle.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

Pas à pas sur [5, 3, 8, 1] :

1. 5>3 → échange → [3, 5, 8, 1] — 5 remonte
2. 5<8 → rien → [3, 5, 8, 1]
3. 8>1 → échange → [3, 5, 1, 8] — 8 a remonté jusqu'à la fin !
4. Deuxième tour : 3<5, 5>1 → échange → [3, 1, 5, 8]
5. Dernier tour : 3>1 → échange → [1, 3, 5, 8] ✅

⏱ Complexité : O(n²) dans tous les cas. Simple à comprendre, lent en pratique.

---

2. Insertion Sort (Tri par insertion) — O(n²) 📥

Principe : On construit le tableau trié un élément à la fois. On prend chaque élément et on l'insère à sa bonne place parmi les éléments déjà triés (comme quand on trie des cartes à jouer).

Exécution pas à pas
pseudo
1/13
1FONCTION tri_insertion(tableau)2    POUR i ALLANT DE 1 À taille(tableau)-1 FAIRE3        clé ← tableau[i]             ⬅ L'élément à insérer4        j ← i - 1                    ⬅ On commence juste avant5        TANT QUE j ≥ 0 ET tableau[j] > clé FAIRE6            tableau[j+1] ← tableau[j]  ⬅ On décale vers la droite7            j ← j - 18        FIN TANT QUE9        tableau[j+1] ← clé             ⬅ On place la clé au bon endroit10    FIN POUR11    RETOURNER tableau12FIN FONCTION13 
🧩
FONCTION tri_insertion(tableau)
FONCTION tri_insertion(tableau)Le programme exécute cette action, puis passe à la suivante.
On définit une fonction appelée "tri_insertion(tableau)". Cette fonction contient des instructions qui seront exécutées quand on l'appelle.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]    # L'élément à insérer
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]  # Décalage
            j -= 1
        arr[j + 1] = key  # Insertion
    return arr

Pas à pas sur [5, 3, 8, 1] :

1. i=1, clé=3. 5>3 → décale → [5, 5, 8, 1] → insère 3 → [3, 5, 8, 1]
2. i=2, clé=8. 5<8 → rien → [3, 5, 8, 1]
3. i=3, clé=1. 8>1, 5>1, 3>1 → décale → [3, 5, 8, 8] → [3, 5, 5, 8] → [3, 3, 5, 8] → insère 1 → [1, 3, 5, 8] ✅

💡 Performant sur les petits tableaux et les tableaux presque triés (O(n) au meilleur cas).

---

3. Merge Sort (Tri fusion) — O(n log n) 🧩

Principe : Diviser pour régner (divide and conquer).

1. Diviser le tableau en deux moitiés
2. Trier récursivement chaque moitié
3. Fusionner les deux moitiés triées

Exécution pas à pas
pseudo
1/31
1FONCTION tri_fusion(tableau)2    SI taille(tableau) ≤ 1 ALORS3        RETOURNER tableau              ⬅ Cas de base : déjà trié4    FIN SI5    6    milieu ← taille(tableau) / 27    gauche ← tri_fusion(tableau[0..milieu])    ⬅ Diviser + trier récursivement8    droite ← tri_fusion(tableau[milieu..fin])9    10    RETOURNER fusionner(gauche, droite)       ⬅ Fusionner les deux parties triées11FIN FONCTION12 13FONCTION fusionner(gauche, droite)14    résultat ← []15    i ← 0, j ← 016    17    TANT QUE i < taille(gauche) ET j < taille(droite) FAIRE18        SI gauche[i] ≤ droite[j] ALORS19            résultat.ajouter(gauche[i])   ⬅ Prendre le plus petit des deux20            i ← i + 121        SINON22            résultat.ajouter(droite[j])23            j ← j + 124        FIN SI25    FIN TANT QUE26    27    résultat.ajouter_tous(gauche[i..fin])  ⬅ Ajouter les restes28    résultat.ajouter_tous(droite[j..fin])29    RETOURNER résultat30FIN FONCTION31 
🧩
FONCTION tri_fusion(tableau)
FONCTION tri_fusion(tableau)Le programme exécute cette action, puis passe à la suivante.
On définit une fonction appelée "tri_fusion(tableau)". Cette fonction contient des instructions qui seront exécutées quand on l'appelle.

def tri_fusion(tab):
    if len(tab) <= 1:
        return tab
    milieu = len(tab) // 2
    gauche = tri_fusion(tab[:milieu])
    droite = tri_fusion(tab[milieu:])
    return fusionner(gauche, droite)

def fusionner(g, d):
    resultat = []
    i = j = 0
    while i < len(g) and j < len(d):
        if g[i] <= d[j]:
            resultat.append(g[i])
            i += 1
        else:
            resultat.append(d[j])
            j += 1
    resultat.extend(g[i:])
    resultat.extend(d[j:])
    return resultat

tab = [8, 3, 5, 1, 9, 2]
print(tri_fusion(tab))  # [1, 2, 3, 5, 8, 9]

Visualisation : [8, 3, 5, 1, 9, 2]

1. Diviser → [8, 3, 5] et [1, 9, 2]
2. Diviser → [8] [3, 5] et [1, 9] [2]
3. Trier → [8] [3, 5] et [1, 9] [2]
4. Fusionner → [3, 5, 8] et [1, 2, 9]
5. Fusionner → [1, 2, 3, 5, 8, 9] ✅

⏱ Toujours O(n log n) — même complexité dans le meilleur et le pire cas. Stable et prévisible.

---

4. Quick Sort (Tri rapide) — O(n log n) en moyenne ⚡

Principe : Choisir un pivot, partitionner le tableau autour de ce pivot, puis trier récursivement chaque partition.

Exécution pas à pas
pseudo
1/12
1FONCTION tri_rapide(tableau)2    SI taille(tableau) ≤ 1 ALORS3        RETOURNER tableau4    5    pivot ← tableau[milieu]                  ⬅ Choisir un pivot6    gauche ← éléments < pivot               ⬅ Partitionner7    milieu ← éléments == pivot8    droite ← éléments > pivot9    10    RETOURNER tri_rapide(gauche) + milieu + tri_rapide(droite)11FIN FONCTION12 
🧩
FONCTION tri_rapide(tableau)
FONCTION tri_rapide(tableau)Le programme exécute cette action, puis passe à la suivante.
On définit une fonction appelée "tri_rapide(tableau)". Cette fonction contient des instructions qui seront exécutées quand on l'appelle.

def tri_rapide(tab):
    if len(tab) <= 1:
        return tab
    pivot = tab[len(tab) // 2]
    gauche = [x for x in tab if x < pivot]
    milieu = [x for x in tab if x == pivot]
    droite = [x for x in tab if x > pivot]
    return tri_rapide(gauche) + milieu + tri_rapide(droite)

tab = [8, 3, 5, 1, 9, 2]
print(tri_rapide(tab))  # [1, 2, 3, 5, 8, 9]

💡 Rapide en pratique mais O(n²) dans le pire cas (pivot mal choisi). C'est le tri le plus utilisé dans les langages.

---

5. Comparaison des tris ⚖️

Quand utiliser quoi ?

• Insertion : petits tableaux (< 50 éléments) ou presque triés
• Merge : quand la stabilité et la prévisibilité comptent
• Quick : usage général, grands tableaux
• Bubble : à éviter en pratique (pédagogique uniquement)

---

6. Recherche dichotomique (Binary Search) — O(log n) 🎯

Une fois le tableau trié, on peut chercher très rapidement :

Exécution pas à pas
pseudo
1/19
1FONCTION recherche_dichotomique(tableau, cible)2    gauche ← 03    droite ← taille(tableau) - 14    5    TANT QUE gauche ≤ droite FAIRE6        milieu ← (gauche + droite) / 27        8        SI tableau[milieu] == cible ALORS9            RETOURNER milieu           ⬅ Trouvé !10        SINON SI tableau[milieu] < cible ALORS11            gauche ← milieu + 1        ⬅ Chercher à droite12        SINON13            droite ← milieu - 1        ⬅ Chercher à gauche14        FIN SI15    FIN TANT QUE16    17    RETOURNER -1                       ⬅ Pas trouvé18FIN FONCTION19 
🧩
FONCTION recherche_dichotomique(tableau, cible)
FONCTION recherche_dichotomique(tableau, cible)Le programme exécute cette action, puis passe à la suivante.
On définit une fonction appelée "recherche_dichotomique(tableau, cible)". Cette fonction contient des instructions qui seront exécutées quand on l'appelle.

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

tab = [1, 3, 5, 7, 9, 11, 13]
print(binary_search(tab, 7))  # 3

💡 Avec 1 million d'éléments triés, la recherche dichotomique trouve la réponse en ~20 étapes (log₂ 1 000 000 ≈ 20). Une recherche linéaire en prendrait 500 000 en moyenne !

---

Exercices pour toi 🎯

1. Implémente Bubble Sort avec une optimisation : arrête-toi si aucune permutation n'a eu lieu pendant un tour
2. Merge Sort récursif : trace les appels récursifs pour [4, 2, 7, 1]
3. Binary Search : trouve le point d'insertion d'une valeur dans un tableau trié
4. Compare les temps d'exécution des 4 tris sur [100, 1000, 10000] éléments