27 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.

27.1 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

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

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

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

Tri avec une fonction clé

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

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]))

['banane', 'fraise', 'kiwi', 'pomme']
['kiwi', 'pomme', 'banane', 'fraise']
['banane', 'pomme', 'fraise', 'kiwi']

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.

# 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))

[('Alice', 14), ('Bob', 8), ('Charlie', 17), ('Diana', 9)]
[('Bob', 8), ('Diana', 9), ('Alice', 14), ('Charlie', 17)]
[('Charlie', 17), ('Alice', 14), ('Diana', 9), ('Bob', 8)]

Avec operator.itemgetter (alternative)

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

from operator import itemgetter

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

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

[('Bob', 8), ('Alice', 14), ('Charlie', 17)]

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.

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}")

1. Charlie : 17
2. Alice : 14
3. Diana : 9
4. Bob : 8

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.

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]))

[('Alice', 14), ('Bob', 14), ('Diana', 14), ('Charlie', 17)]

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.

27.2 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.

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]))

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

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.

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]))

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

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.

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]))

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

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

À retenir pour le TOSA

Python utilise Timsort (O(n log n)) — vous ne réimplémenterez jamais un tri.
Les algorithmes O(n²) ci-dessus sont vus pour la culture et la compréhension.
Complexité = temps de calcul en fonction de la taille de l’entrée. On en reparle en Partie 3.

27.3 Recherche dans une liste

Deux approches : séquentielle (chercher partout) et dichotomique (si la liste est triée).

Recherche séquentielle (linéaire)

Principe : on parcourt la liste élément par élément jusqu’à trouver la cible.

def recherche_sequentielle(liste, cible):
    for i, x in enumerate(liste):
        if x == cible:
            return i              # indice trouvé
    return -1                     # absent

print(recherche_sequentielle([5, 2, 8, 1, 9, 3], 8))      # 2
print(recherche_sequentielle([5, 2, 8, 1, 9, 3], 99))     # -1

2
-1

Complexité : O(n) — au pire, on parcourt toute la liste.

C’est aussi ce que fait l’opérateur in sur une liste :

liste = [5, 2, 8, 1, 9, 3]
print(8 in liste)       # True
print(99 in liste)      # False

True
False

Recherche dichotomique (ou binaire)

Principe : sur une liste triée, on regarde l’élément du milieu. Selon qu’il est plus grand ou plus petit que la cible, on élimine la moitié restante.

def recherche_dichotomique(liste_triee, cible):
    gauche, droite = 0, len(liste_triee) - 1

    while gauche <= droite:
        milieu = (gauche + droite) // 2
        if liste_triee[milieu] == cible:
            return milieu
        elif liste_triee[milieu] < cible:
            gauche = milieu + 1
        else:
            droite = milieu - 1

    return -1

# Démonstration (attention : la liste DOIT être triée)
triee = [1, 3, 5, 8, 12, 17, 25, 40]
print(recherche_dichotomique(triee, 12))      # 4
print(recherche_dichotomique(triee, 99))      # -1

4
-1

Complexité : O(log n) — divisé par deux à chaque étape. Sur 1 million d’éléments, 20 itérations suffisent (là où la recherche séquentielle en ferait 1 million).

Condition d’application : liste triée !

La dichotomie ne fonctionne que sur une liste triée. Si vous devez faire de nombreuses recherches, trier d’abord peut valoir le coup :

Trier : O(n log n), une fois.
Chaque recherche : O(log n) au lieu de O(n).

Si vous faites k recherches : total = O(n log n + k log n) contre O(k × n) en séquentiel. Dès que k est grand, la dichotomie gagne largement.

La bibliothèque standard le fait pour vous

Python propose le module bisect qui implémente la dichotomie :

import bisect

triee = [1, 3, 5, 8, 12, 17, 25, 40]

# Position d'insertion pour garder la liste triée
print(bisect.bisect_left(triee, 12))      # 4
print(bisect.bisect_left(triee, 10))      # 3 (entre 8 et 12)

4
4

27.4 Modéliser un graphe (découverte)

Un graphe est une structure qui modélise des relations entre objets : réseau social, carte routière, dépendances entre tâches…

Les objets sont appelés sommets (ou nœuds).
Les relations sont appelées arêtes (ou arcs si orientés).

Représentation par dictionnaire d’adjacence

La manière la plus simple de modéliser un graphe en Python :

# Exemple : un petit réseau social
# "Alice est amie avec Bob et Charlie"
amis = {
    "Alice":   ["Bob", "Charlie"],
    "Bob":     ["Alice", "Diana"],
    "Charlie": ["Alice"],
    "Diana":   ["Bob", "Eve"],
    "Eve":     ["Diana"],
}

# Les amis d'Alice
print("Amis d'Alice :", amis["Alice"])

# Tous les sommets (personnes)
print("Personnes :", list(amis.keys()))

# Une personne est-elle dans le réseau ?
print("Frank est dans le réseau ?", "Frank" in amis)

Amis d'Alice : ['Bob', 'Charlie']
Personnes : ['Alice', 'Bob', 'Charlie', 'Diana', 'Eve']
Frank est dans le réseau ? False

Opérations de base

amis = {
    "Alice":   ["Bob", "Charlie"],
    "Bob":     ["Alice", "Diana"],
    "Charlie": ["Alice"],
    "Diana":   ["Bob", "Eve"],
    "Eve":     ["Diana"],
}

# Nombre d'amis (degré)
def nb_amis(graphe, personne):
    return len(graphe.get(personne, []))

print("Alice a", nb_amis(amis, "Alice"), "amis")
print("Eve a", nb_amis(amis, "Eve"), "amis")

# Amis en commun
def amis_communs(graphe, a, b):
    return set(graphe.get(a, [])) & set(graphe.get(b, []))

print("Alice ∩ Bob :", amis_communs(amis, "Alice", "Bob"))

Alice a 2 amis
Eve a 1 amis
Alice ∩ Bob : set()

Parcours en largeur (BFS) — pour culture

Trouver tous les « amis d’amis » d’une personne (voisinage étendu) :

from collections import deque

amis = {
    "Alice":   ["Bob", "Charlie"],
    "Bob":     ["Alice", "Diana"],
    "Charlie": ["Alice"],
    "Diana":   ["Bob", "Eve"],
    "Eve":     ["Diana"],
}

def parcourir(graphe, depart):
    """Renvoie tous les sommets atteignables depuis 'depart'."""
    visites = set()
    a_visiter = deque([depart])

    while a_visiter:
        actuel = a_visiter.popleft()
        if actuel in visites:
            continue
        visites.add(actuel)
        for voisin in graphe.get(actuel, []):
            if voisin not in visites:
                a_visiter.append(voisin)

    return visites

print("Accessible depuis Alice :", parcourir(amis, "Alice"))

Accessible depuis Alice : {'Eve', 'Bob', 'Charlie', 'Alice', 'Diana'}

Cet algorithme (BFS pour Breadth-First Search) visite les sommets de proche en proche. Il n’est pas indispensable pour le niveau Opérationnel, mais comprendre le principe est un plus au TOSA.

Pour aller plus loin

Des bibliothèques comme networkx fournissent des dizaines d’algorithmes sur les graphes (plus courts chemins, composantes connexes, détection de cycles, etc.). Au niveau Opérationnel, savoir modéliser un graphe avec un dict est suffisant ; les algorithmes avancés sont du ressort du Expert.

🧩 Quiz 8.1 — Algorithmique

Question 1

Que renvoie sorted([(1, "b"), (2, "a"), (1, "a")]) ?

[(1, "a"), (1, "b"), (2, "a")]
[(2, "a"), (1, "a"), (1, "b")]
[(1, "b"), (2, "a"), (1, "a")]
Une erreur

🔍 Réponse

a) [(1, "a"), (1, "b"), (2, "a")] — les tuples sont comparés élément par élément : d’abord le premier (1 < 2), en cas d’égalité, le second (“a” < “b”).

print(sorted([(1, "b"), (2, "a"), (1, "a")]))

[(1, 'a'), (1, 'b'), (2, 'a')]

Question 2

Que renvoie sorted([3, 1, 2], key=lambda x: -x) ?

[1, 2, 3]
[3, 2, 1]
[-3, -2, -1]
Une erreur

🔍 Réponse

b) [3, 2, 1] — en triant par -x croissant, on obtient x décroissant. Équivalent à reverse=True.

print(sorted([3, 1, 2], key=lambda x: -x))
print(sorted([3, 1, 2], reverse=True))

[3, 2, 1]
[3, 2, 1]

Question 3

Sur quelle condition la recherche dichotomique fonctionne-t-elle ?

La liste contient uniquement des entiers
La liste est triée
La liste contient moins de 1000 éléments
Aucune condition

🔍 Réponse

b) La liste est triée — la dichotomie élimine la moitié de la liste à chaque étape en comparant avec le milieu. Cela n’a de sens que sur une liste ordonnée.

Question 4

Quelle est la complexité de la recherche dichotomique sur une liste de n éléments ?

O(1)
O(log n)
O(n)
O(n²)

🔍 Réponse

b) O(log n) — à chaque étape, on élimine la moitié. Sur 1 million d’éléments, environ 20 itérations suffisent. C’est énormément plus rapide que la recherche séquentielle (O(n)) sur de gros volumes.

Question 5

Comment trier un dictionnaire d par ses valeurs dans l’ordre décroissant ?

sorted(d, reverse=True)
d.sort(reverse=True)
sorted(d.items(), key=lambda t: t[1], reverse=True)
sorted(d.values(), reverse=True)

🔍 Réponse

c) — on trie les paires (d.items()) en extrayant la valeur avec la clé t[1]. L’option d) ne donne que les valeurs sans les clés.

d = {"Alice": 14, "Bob": 17, "Charlie": 9}
print(sorted(d.items(), key=lambda t: t[1], reverse=True))

[('Bob', 17), ('Alice', 14), ('Charlie', 9)]

Question 6

Que signifie « le tri Python est stable » ?

Il ne plante jamais
Les éléments égaux conservent leur ordre initial
Il trie en place
Il est déterministe

🔍 Réponse

b) Les éléments égaux conservent leur ordre initial — c’est une propriété mathématique du tri. Utile pour des tris en cascade.

# On trie par note. Alice et Diana ont 14 toutes les deux.
etudiants = [("Alice", 14), ("Bob", 17), ("Diana", 14)]
print(sorted(etudiants, key=lambda t: t[1]))
# Alice reste AVANT Diana, leur ordre d'entrée est préservé

[('Alice', 14), ('Diana', 14), ('Bob', 17)]

Question 7

Quelle structure Python est la plus adaptée pour modéliser un graphe non orienté ?

list
tuple
dict de list (ou de set)
set

🔍 Réponse

c) dict de list (ou de set) — chaque clé est un sommet, chaque valeur est la liste de ses voisins. C’est la liste d’adjacence, représentation la plus courante et efficace.

✏️ Exercice 8.1 — Classement d’étudiants

Vous avez une liste d’étudiants avec leur nom, note et nombre de jours d’absence :

etudiants = [
    ("Alice",   14, 2),
    ("Bob",      8, 5),
    ("Charlie", 17, 0),
    ("Diana",   14, 1),
    ("Eve",     12, 3),
]

Produisez 3 classements différents :

Par note décroissante.
Par absences croissantes.
Par note décroissante, puis, en cas d’ex æquo, par absences croissantes.

etudiants = [
    ("Alice",   14, 2),
    ("Bob",      8, 5),
    ("Charlie", 17, 0),
    ("Diana",   14, 1),
    ("Eve",     12, 3),
]

# 1. Par note décroissante
...

# 2. Par absences croissantes
...

# 3. Par note décroissante puis absences croissantes
...

etudiants = [
    ("Alice",   14, 2),
    ("Bob",      8, 5),
    ("Charlie", 17, 0),
    ("Diana",   14, 1),
    ("Eve",     12, 3),
]

# 1. Par note décroissante
tri1 = sorted(etudiants, key=lambda t: t[1], reverse=True)
print("Par note :")
for x in tri1:
    print(" ", x)

# 2. Par absences croissantes
tri2 = sorted(etudiants, key=lambda t: t[2])
print("\nPar absences :")
for x in tri2:
    print(" ", x)

# 3. Multi-critères : par note décroissante, puis absences croissantes
# On utilise un tuple pour la clé : (-note, absences)
tri3 = sorted(etudiants, key=lambda t: (-t[1], t[2]))
print("\nPar note décroissante puis absences croissantes :")
for x in tri3:
    print(" ", x)

Par note :
  ('Charlie', 17, 0)
  ('Alice', 14, 2)
  ('Diana', 14, 1)
  ('Eve', 12, 3)
  ('Bob', 8, 5)

Par absences :
  ('Charlie', 17, 0)
  ('Diana', 14, 1)
  ('Alice', 14, 2)
  ('Eve', 12, 3)
  ('Bob', 8, 5)

Par note décroissante puis absences croissantes :
  ('Charlie', 17, 0)
  ('Diana', 14, 1)
  ('Alice', 14, 2)
  ('Eve', 12, 3)
  ('Bob', 8, 5)

key=lambda t: (-t[1], t[2]) trie d’abord par -t[1] (équivalent à décroissant), puis à égalité, par t[2] (croissant). Les tuples sont comparés élément par élément.

Alternative avec la stabilité du tri :

# Trier d'abord par le critère secondaire
tri = sorted(etudiants, key=lambda t: t[2])       # absences croissantes
# Puis par le critère principal (le tri stable préserve l'ordre secondaire)
tri = sorted(tri, key=lambda t: t[1], reverse=True)    # note décroissante

for x in tri:
    print(x)

('Charlie', 17, 0)
('Diana', 14, 1)
('Alice', 14, 2)
('Eve', 12, 3)
('Bob', 8, 5)

Les deux approches donnent le même résultat.

✏️ Exercice 8.2 — Implémenter la recherche dichotomique

Implémentez dicho(liste_triee, cible) qui renvoie l’indice de cible si présente, -1 sinon. Testez-la avec plusieurs cas.

def dicho(liste, cible):
    ...

# Tests
triee = [1, 3, 5, 8, 12, 17, 25, 40]
print(dicho(triee, 12))
print(dicho(triee, 1))
print(dicho(triee, 40))
print(dicho(triee, 99))

def dicho(liste, cible):
    gauche, droite = 0, len(liste) - 1
    while gauche <= droite:
        milieu = (gauche + droite) // 2
        if liste[milieu] == cible:
            return milieu
        elif liste[milieu] < cible:
            gauche = milieu + 1
        else:
            droite = milieu - 1
    return -1

triee = [1, 3, 5, 8, 12, 17, 25, 40]
print(dicho(triee, 12))    # 4
print(dicho(triee, 1))     # 0
print(dicho(triee, 40))    # 7
print(dicho(triee, 99))    # -1
print(dicho([], 5))        # -1 (liste vide)

On peut instrumenter la fonction pour compter les itérations :

def dicho_instr(liste, cible):
    iterations = 0
    gauche, droite = 0, len(liste) - 1
    while gauche <= droite:
        iterations += 1
        milieu = (gauche + droite) // 2
        if liste[milieu] == cible:
            return milieu, iterations
        elif liste[milieu] < cible:
            gauche = milieu + 1
        else:
            droite = milieu - 1
    return -1, iterations

# Sur une liste de 1 million d'éléments
grande = list(range(1_000_000))
indice, iters = dicho_instr(grande, 999_999)
print(f"Recherche dans {len(grande)} éléments : {iters} itérations")

Recherche dans 1000000 éléments : 20 itérations

20 itérations pour chercher dans 1 million d’éléments — c’est la puissance du O(log n).

✏️ Exercice 8.3 — Amis en commun

À partir de ce graphe d’amitiés :

amis = {
    "Alice":   ["Bob", "Charlie", "Diana"],
    "Bob":     ["Alice", "Eve"],
    "Charlie": ["Alice", "Diana", "Frank"],
    "Diana":   ["Alice", "Charlie", "Eve"],
    "Eve":     ["Bob", "Diana"],
    "Frank":   ["Charlie"],
}

Écrivez :

nb_amis(graphe, personne) — nombre d’amis d’une personne.
amis_communs(graphe, a, b) — ensemble des amis communs à a et b.
personne_plus_populaire(graphe) — la personne avec le plus d’amis.

amis = {
    "Alice":   ["Bob", "Charlie", "Diana"],
    "Bob":     ["Alice", "Eve"],
    "Charlie": ["Alice", "Diana", "Frank"],
    "Diana":   ["Alice", "Charlie", "Eve"],
    "Eve":     ["Bob", "Diana"],
    "Frank":   ["Charlie"],
}

def nb_amis(graphe, personne): ...
def amis_communs(graphe, a, b): ...
def personne_plus_populaire(graphe): ...

amis = {
    "Alice":   ["Bob", "Charlie", "Diana"],
    "Bob":     ["Alice", "Eve"],
    "Charlie": ["Alice", "Diana", "Frank"],
    "Diana":   ["Alice", "Charlie", "Eve"],
    "Eve":     ["Bob", "Diana"],
    "Frank":   ["Charlie"],
}

def nb_amis(graphe, personne):
    return len(graphe.get(personne, []))

def amis_communs(graphe, a, b):
    return set(graphe.get(a, [])) & set(graphe.get(b, []))

def personne_plus_populaire(graphe):
    return max(graphe, key=lambda p: len(graphe[p]))

print("Nb amis Alice :", nb_amis(amis, "Alice"))
print("Nb amis Frank :", nb_amis(amis, "Frank"))

print("Alice ∩ Diana :", amis_communs(amis, "Alice", "Diana"))
print("Alice ∩ Bob   :", amis_communs(amis, "Alice", "Bob"))

print("Plus populaire :", personne_plus_populaire(amis))

Nb amis Alice : 3
Nb amis Frank : 1
Alice ∩ Diana : {'Charlie'}
Alice ∩ Bob   : set()
Plus populaire : Alice

def top_populaires(graphe, n=3):
    classement = sorted(graphe, key=lambda p: len(graphe[p]), reverse=True)
    return classement[:n]

print("Top 3 :", top_populaires(amis))

Top 3 : ['Alice', 'Charlie', 'Diana']

✏️ Exercice 8.4 — Vérifier la symétrie d’un graphe d’amitiés

Dans un réseau d’amis, si A est l’ami de B, alors B devrait aussi avoir A dans ses amis. Écrivez une fonction qui vérifie la symétrie d’un graphe d’amitiés et renvoie la liste des paires asymétriques (anomalies).

amis = {
    "Alice":   ["Bob", "Charlie"],
    "Bob":     ["Alice"],        # OK : Alice a Bob
    "Charlie": [],                # ANOMALIE : Alice a Charlie mais pas l'inverse
}

def verifier_symetrie(graphe):
    """Renvoie la liste des paires (a, b) où a a b comme ami mais pas l'inverse."""
    ...

print(verifier_symetrie(amis))

def verifier_symetrie(graphe):
    anomalies = []
    for a, liste_a in graphe.items():
        for b in liste_a:
            if a not in graphe.get(b, []):
                anomalies.append((a, b))
    return anomalies

amis = {
    "Alice":   ["Bob", "Charlie"],
    "Bob":     ["Alice"],
    "Charlie": [],
}

print(verifier_symetrie(amis))

[('Alice', 'Charlie')]

Chaque tuple (a, b) signifie : « a a b dans ses amis, mais b n’a pas a ».

def symetriser(graphe):
    """Renvoie une copie symétrique du graphe."""
    resultat = {k: list(v) for k, v in graphe.items()}
    for a, liste_a in graphe.items():
        for b in liste_a:
            if b not in resultat:
                resultat[b] = []
            if a not in resultat[b]:
                resultat[b].append(a)
    return resultat

amis = {"Alice": ["Bob", "Charlie"], "Bob": ["Alice"], "Charlie": []}

for k, v in symetriser(amis).items():
    print(f"{k} : {v}")

Alice : ['Bob', 'Charlie']
Bob : ['Alice']
Charlie : ['Alice']

À retenir

Points clés du chapitre

sorted() avec key= est la clé du tri personnalisé. key=lambda t: t[i] pour trier par un champ.
Tri multi-critères : key=lambda t: (-t[1], t[2]) — tuple avec signe négatif pour inverser un critère.
Le tri Python est stable — les égaux conservent leur ordre initial.
Algorithmes de tri O(n²) : sélection, insertion, bulles. Python utilise Timsort (O(n log n)).
Recherche séquentielle : O(n), fonctionne partout.
Recherche dichotomique : O(log n), nécessite une liste triée. Module bisect.
Modéliser un graphe avec un dict de listes (liste d’adjacence).

← Chapitre précédent : Modules • Chapitre suivant : Extraction de données →

27.1 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

27.2 Les algorithmes de tri de base (culture)

Tri par sélection

Tri par insertion

Tri à bulles

27.3 Recherche dans une liste

Recherche séquentielle (linéaire)

Recherche dichotomique (ou binaire)

La bibliothèque standard le fait pour vous

27.4 Modéliser un graphe (découverte)

Représentation par dictionnaire d’adjacence

Opérations de base

Parcours en largeur (BFS) — pour culture

🧩 Quiz 8.1 — Algorithmique

Question 1

Question 2

Question 3

Question 4

Question 5

Question 6

Question 7

✏️ Exercice 8.1 — Classement d’étudiants

✏️ Exercice 8.2 — Implémenter la recherche dichotomique

✏️ Exercice 8.3 — Amis en commun

✏️ Exercice 8.4 — Vérifier la symétrie d’un graphe d’amitiés

À retenir

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