Algorithmes classiques : tri, recherche, graphes

Un algorithme est une séquence d'étapes pour résoudre un problème. Ce chapitre aborde trois familles essentielles : le tri (avec ses finesses), la recherche (séquentielle vs dichotomique), et une introduction à la modélisation de graphes. L'objectif : vous donner les réflexes algorithmiques du niveau Opérationnel.

Trier : `sorted()` et `.sort()` revisités

Rappel des deux outils de tri (vus en Partie 1) :

	`liste.sort()`	`sorted(iterable)`
Modifie en place	✅	❌
Renvoie	`None`	Nouvelle liste
Sur un tuple/chaîne	❌ (tuples immuables)	✅

Tri croissant / décroissant

python

notes = [12, 15, 9, 17, 11]

print(sorted(notes))                  # croissant (défaut)
print(sorted(notes, reverse=True))    # décroissant

Tri avec une fonction clé

Le paramètre key accepte une fonction qui extrait la valeur de tri pour chaque élément.

python

mots = ["banane", "kiwi", "pomme", "fraise"]

# Par ordre alphabétique (défaut)
print(sorted(mots))

# Par longueur
print(sorted(mots, key=len))

# Par dernière lettre
print(sorted(mots, key=lambda m: m[-1]))

La syntaxe lambda m: m[-1] définit une fonction anonyme qui renvoie la dernière lettre. Les lambdas sont vues en détail en Partie 3 — à ce stade, acceptez cette syntaxe.

Tri de listes de tuples

C'est un cas très fréquent : on a une liste de tuples et on veut trier selon un élément spécifique.

python

# Liste de (prenom, note)
etudiants = [
    ("Alice",   14),
    ("Bob",      8),
    ("Charlie", 17),
    ("Diana",    9),
]

# Par défaut : trie selon le PREMIER élément (le prénom)
print(sorted(etudiants))

# Par note (deuxième élément)
print(sorted(etudiants, key=lambda t: t[1]))

# Par note décroissante
print(sorted(etudiants, key=lambda t: t[1], reverse=True))

Avec operator.itemgetter (alternative)

La bibliothèque standard operator offre une alternative plus rapide à lambda t: t[1] :

python

from operator import itemgetter

etudiants = [("Alice", 14), ("Bob", 8), ("Charlie", 17)]

print(sorted(etudiants, key=itemgetter(1)))

C'est équivalent à lambda t: t[1] mais plus rapide sur de grandes listes.

Tri d'un dictionnaire par valeurs

Un dictionnaire n'est pas directement triable — mais ses items (paires clé/valeur) le sont.

python

scores = {"Alice": 14, "Bob": 8, "Charlie": 17, "Diana": 9}

# Trier par valeur décroissante
classement = sorted(scores.items(), key=lambda t: t[1], reverse=True)

for rang, (nom, score) in enumerate(classement, start=1):
    print(f"{rang}. {nom} : {score}")

Tri stable

Le tri Python est stable

Quand deux éléments ont la même clé de tri, leur ordre relatif initial est conservé. C'est une propriété importante pour des tris en plusieurs passes.

python

etudiants = [
    ("Alice",   14),
    ("Bob",     14),      # même note qu'Alice
    ("Charlie", 17),
    ("Diana",   14),      # même note encore
]

# Tri par note : Alice, Bob, Diana restent dans l'ordre initial
print(sorted(etudiants, key=lambda t: t[1]))

Cette propriété permet de trier en cascade : d'abord par un critère secondaire, puis par le critère principal. Le résultat final respecte les deux ordres.

Les algorithmes de tri de base (culture)

Python utilise en interne Timsort, un algorithme hybride très performant (complexité O(n log n)). Vous n'avez pas à réimplémenter le tri dans la vraie vie. Mais le TOSA peut interroger sur les algorithmes de base, parce que c'est de la culture algorithmique.

Tri par sélection

Principe : à chaque étape, trouver le plus petit élément restant et le placer en tête.

python

def tri_selection(liste):
    liste = liste.copy()     # on ne modifie pas l'original
    n = len(liste)
    for i in range(n):
        # Trouver l'indice du minimum dans liste[i:]
        i_min = i
        for j in range(i + 1, n):
            if liste[j] < liste[i_min]:
                i_min = j
        # Échanger liste[i] et liste[i_min]
        liste[i], liste[i_min] = liste[i_min], liste[i]
    return liste

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

Complexité : O(n²). Simple à comprendre, lent en pratique.

Tri par insertion

Principe : on construit le résultat progressivement en insérant chaque élément à sa place dans la partie déjà triée.

python

def tri_insertion(liste):
    liste = liste.copy()
    for i in range(1, len(liste)):
        val = liste[i]
        j = i - 1
        # Décaler vers la droite les éléments > val
        while j >= 0 and liste[j] > val:
            liste[j + 1] = liste[j]
            j -= 1
        liste[j + 1] = val
    return liste

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

Complexité : O(n²) dans le pire cas, mais très rapide si la liste est presque triée.

Tri à bulles

Principe : comparer les éléments adjacents et les échanger si mal ordonnés. On fait plusieurs passages jusqu'à ce que plus rien ne bouge.

python

def tri_bulles(liste):
    liste = liste.copy()
    n = len(liste)
    for i in range(n):
        echange = False
        for j in range(n - i - 1):
            if liste[j] > liste[j + 1]:
                liste[j], liste[j + 1] = liste[j + 1], liste[j]
                echange = True
        if not echange:
            break       # déjà trié, on sort
    return liste

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

Complexité : O(n²). Didactique mais peu performant.

Trier : sorted() et .sort() revisités

Tri croissant / décroissant

Tri avec une fonction clé

Tri de listes de tuples

Tri d'un dictionnaire par valeurs

Tri stable

Les algorithmes de tri de base (culture)

Tri par sélection

Tri par insertion

Tri à bulles

Débloquez l'intégralité du parcours

Trier : `sorted()` et `.sort()` revisités