Plan d'apprentissage

Les algorithmes de tri — Programme intensif de 24 heures

Un parcours structuré en 9 modules pour comprendre, implémenter et comparer les

principaux algorithmes de tri, avec pour chaque module un résumé de cours, des
exercices pratiques et leurs corrections complètes en Python.

24 heures · 9 modules · 27+ exercices corrigés

Module Sujet Durée

1 Fondamentaux : complexité et notation Big O 2h

2 Tri à bulles (Bubble Sort) 2h

3 Tri par sélection (Selection Sort) 2h

4 Tri par insertion (Insertion Sort) 2h

5 Tri fusion (Merge Sort) 4h

6 Tri rapide (Quick Sort) 4h

7 Tri par tas (Heap Sort) 3h

8 Tri par comptage et Tri par base (Counting / Radix Sort) 3h

9 Synthèse, comparaison et projet final 2h

Total 24h

Page 1 / 22
 Module 1 — Fondamentaux : complexité et notation Big
O

Durée : 2h Niveau : débutant Prérequis : bases de Python (boucles, listes)

Résumé de la leçon
Avant d'étudier un algorithme de tri, il faut savoir comment mesurer son efficacité. La complexité algorithmique
décrit comment le temps d'exécution (complexité temporelle) et la mémoire utilisée (complexité spatiale) évoluent en
fonction de la taille n des données. On utilise la notation Big O pour exprimer le pire des cas.

Classes de complexité courantes (de la plus rapide à la plus lente) :

O(1) — constant
O(log n) — logarithmique
O(n) — linéaire

O(n log n) — quasi-linéaire (les meilleurs tris comparatifs)

O(n²) — quadratique (tris simples)

On distingue aussi la stabilité d'un tri (deux éléments égaux gardent-ils leur ordre relatif ?) et le fait qu'il soit en place
(utilise-t-il peu de mémoire supplémentaire, O(1) ou O(log n) ?).

✏️Exercices

Exercice 1.1 — Estimer la complexité

Donnez la complexité (en notation Big O) des trois extraits de code Python suivants :

# A
for i in range(n):
print(i)

# B
for i in range(n):
for j in range(n):
print(i, j)

# C
i = 1
while i < n:
i = i * 2

✅ Réponse 1.1

A : une seule boucle de taille n → O(n)

B : deux boucles imbriquées de taille n → O(n²)
C : i double à chaque itération, il faut environ log₂(n) itérations pour dépasser n → O(log n)

Exercice 1.2 — Chronométrer un algorithme

Écrivez une fonction Python mesurer_temps(fonction, *args) qui exécute une fonction donnée et affiche son
temps d'exécution en millisecondes.

✅ Réponse 1.2

import time

def mesurer_temps(fonction, *args):

debut = time.perf_counter()

Page 2 / 22
 resultat = fonction(*args)
fin = time.perf_counter()
print(f"Temps d'exécution : {(fin - debut) * 1000:.4f} ms")
return resultat

# Exemple d'utilisation
def somme_liste(liste):
return sum(liste)

mesurer_temps(somme_liste, list(range(1000000)))

Exercice 1.3 — Comparer deux approches

Une fonction cherche si un élément existe dans une liste triée de n éléments. Comparez, en Big O, une recherche
linéaire ( in ) contre une recherche binaire ( bisect ). Implémentez les deux et testez-les sur une liste de 100 000
éléments.

✅ Réponse 1.3

import bisect
import time

def recherche_lineaire(liste, cible):

return cible in liste # O(n)

def recherche_binaire(liste, cible):

i = bisect.bisect_left(liste, cible) # O(log n)
return i < len(liste) and liste[i] == cible

liste = list(range(100_000))
cible = 99_999

debut = time.perf_counter()
recherche_lineaire(liste, cible)
print("Linéaire :", time.perf_counter() - debut, "s")

debut = time.perf_counter()
recherche_binaire(liste, cible)
print("Binaire :", time.perf_counter() - debut, "s")

# La recherche binaire (O(log n)) est nettement plus rapide

# que la recherche linéaire (O(n)) quand n est grand.

☑ À la fin de ce module, vous devez savoir lire un algorithme et estimer sa complexité en O(1), O(log n), O(n), O(n log n)
ou O(n²), et savoir mesurer un temps d'exécution en Python.

Page 3 / 22
 Module 2 — Tri à bulles (Bubble Sort)

Durée : 2h Complexité : O(n²) Stable · En place

Résumé de la leçon
Le tri à bulles parcourt la liste plusieurs fois en comparant deux éléments adjacents et en les échangeant s'ils sont dans
le mauvais ordre. À chaque passage, le plus grand élément restant "remonte" (comme une bulle) vers sa position finale.
C'est l'algorithme le plus simple à comprendre, mais aussi l'un des moins efficaces.

Meilleur cas Cas moyen Pire cas Mémoire

O(n) (liste déjà triée, avec optimisation) O(n²) O(n²) O(1)

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

✏️Exercices

Exercice 2.1 — Implémentation de base

Implémentez le tri à bulles pour trier la liste [5, 1, 4, 2, 8] par ordre croissant, sans utiliser l'optimisation
d'arrêt anticipé.

✅ Réponse 2.1

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

print(bubble_sort_simple([5, 1, 4, 2, 8]))
# [1, 2, 4, 5, 8]

Exercice 2.2 — Tri décroissant et comptage des échanges

Modifiez le tri à bulles pour trier une liste par ordre décroissant et retourner en plus le nombre total d'échanges
effectués.

✅ Réponse 2.2

def bubble_sort_decroissant(liste):
n = len(liste)
nb_echanges = 0
for i in range(n - 1):
for j in range(n - 1 - i):
if liste[j] < liste[j + 1]:
liste[j], liste[j + 1] = liste[j + 1], liste[j]
nb_echanges += 1
return liste, nb_echanges

resultat, echanges = bubble_sort_decroissant([5, 1, 4, 2, 8])

Page 4 / 22
 print(resultat, "-> échanges :", echanges)
# [8, 5, 4, 2, 1] -> échanges : 6

Exercice 2.3 — Détecter une liste déjà triée

En utilisant la version optimisée du tri à bulles (avec drapeau echange ), affichez le nombre de passages (itérations
de la boucle externe) nécessaires pour trier [1, 2, 3, 4, 5] (déjà triée) et comparez avec [5, 4, 3, 2, 1] (à
l'envers).

✅ Réponse 2.3

def bubble_sort_avec_comptage(liste):
n = len(liste)
passages = 0
for i in range(n - 1):
echange = False
passages += 1
for j in range(n - 1 - i):
if liste[j] > liste[j + 1]:
liste[j], liste[j + 1] = liste[j + 1], liste[j]
echange = True
if not echange:
break
return liste, passages

print(bubble_sort_avec_comptage([1, 2, 3, 4, 5]))
# ([1, 2, 3, 4, 5], 1) -> un seul passage suffit
print(bubble_sort_avec_comptage([5, 4, 3, 2, 1]))
# ([1, 2, 3, 4, 5], 4) -> il faut n-1 passages

☑ À la fin de ce module, vous devez savoir implémenter le tri à bulles, l'optimiser avec un drapeau d'arrêt, et expliquer
pourquoi sa complexité est O(n²) dans le pire cas.

Page 5 / 22
 Module 3 — Tri par sélection (Selection Sort)

Durée : 2h Complexité : O(n²) Instable · En place

Résumé de la leçon
Le tri par sélection divise la liste en une partie triée (au début) et une partie non triée (à la fin). À chaque itération, il
cherche le minimum de la partie non triée et l'échange avec le premier élément non trié. Contrairement au tri à bulles,
le nombre d'échanges est minimal (au plus n-1), mais le nombre de comparaisons reste toujours O(n²), même si la liste
est déjà triée.

Meilleur cas Cas moyen Pire cas Mémoire

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

def selection_sort(liste):
n = len(liste)
for i in range(n - 1):
indice_min = i
for j in range(i + 1, n):
if liste[j] < liste[indice_min]:
indice_min = j
liste[i], liste[indice_min] = liste[indice_min], liste[i]
return liste

✏️Exercices

Exercice 3.1 — Implémentation de base

Implémentez le tri par sélection pour trier [64, 25, 12, 22, 11] par ordre croissant.

✅ Réponse 3.1

def selection_sort(liste):
n = len(liste)
for i in range(n - 1):
indice_min = i
for j in range(i + 1, n):
if liste[j] < liste[indice_min]:
indice_min = j
liste[i], liste[indice_min] = liste[indice_min], liste[i]
return liste

print(selection_sort([64, 25, 12, 22, 11]))

# [11, 12, 22, 25, 64]

Exercice 3.2 — Trouver le maximum au lieu du minimum

Adaptez le tri par sélection pour qu'il trie la liste en plaçant à chaque itération le maximum à la fin de la partie non
triée (donc un tri croissant, mais construit "par la fin").

✅ Réponse 3.2

def selection_sort_par_max(liste):
n = len(liste)
for i in range(n - 1, 0, -1):
indice_max = i
for j in range(i):
if liste[j] > liste[indice_max]:
indice_max = j
liste[i], liste[indice_max] = liste[indice_max], liste[i]
return liste

Page 6 / 22
 print(selection_sort_par_max([64, 25, 12, 22, 11]))
# [11, 12, 22, 25, 64]

Exercice 3.3 — Compter les comparaisons

Modifiez le tri par sélection pour compter le nombre total de comparaisons effectuées lors du tri d'une liste de 6
éléments, et vérifiez que ce nombre correspond bien à n(n-1)/2.

✅ Réponse 3.3

def selection_sort_comptage(liste):
n = len(liste)
comparaisons = 0
for i in range(n - 1):
indice_min = i
for j in range(i + 1, n):
comparaisons += 1
if liste[j] < liste[indice_min]:
indice_min = j
liste[i], liste[indice_min] = liste[indice_min], liste[i]
return liste, comparaisons

liste = [64, 25, 12, 22, 11, 90]

resultat, comparaisons = selection_sort_comptage(liste)
n = 6
print(resultat, "-> comparaisons :", comparaisons)
print("n(n-1)/2 =", n * (n - 1) // 2)
# comparaisons == 15 == n(n-1)/2 ✔

☑ À la fin de ce module, vous devez savoir pourquoi le tri par sélection fait toujours O(n²) comparaisons, même sur une
liste déjà triée, contrairement au tri à bulles optimisé.

Page 7 / 22
 Module 4 — Tri par insertion (Insertion Sort)

Durée : 2h Complexité : O(n²) / O(n) meilleur cas Stable · En place

Résumé de la leçon
Le tri par insertion construit la liste triée un élément à la fois : il prend chaque élément de la partie non triée et l'insère
à sa bonne place dans la partie déjà triée, en décalant les éléments plus grands. C'est la méthode qu'on utilise
naturellement pour trier des cartes à jouer dans sa main. Très efficace sur des petites listes ou des listes presque triées.

Meilleur cas Cas moyen Pire cas Mémoire

O(n) (déjà triée) O(n²) O(n²) O(1)

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

✏️Exercices

Exercice 4.1 — Implémentation de base

Implémentez le tri par insertion pour trier [12, 11, 13, 5, 6] par ordre croissant.

✅ Réponse 4.1

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

print(insertion_sort([12, 11, 13, 5, 6]))

# [5, 6, 11, 12, 13]

Exercice 4.2 — Insertion dans une liste triée (bisect)

Écrivez une fonction inserer_element(liste_triee, x) qui insère un nouvel élément x dans une liste déjà triée,
en gardant la liste triée, en utilisant le module bisect .

✅ Réponse 4.2

import bisect

def inserer_element(liste_triee, x):

[Link](liste_triee, x)
return liste_triee

liste = [1, 3, 4, 8, 10]

print(inserer_element(liste, 5))
# [1, 3, 4, 5, 8, 10]

Page 8 / 22
Exercice 4.3 — Tri par insertion binaire
Améliorez le tri par insertion en utilisant une recherche binaire (au lieu d'une recherche linéaire) pour trouver la
position d'insertion, ce qui réduit le nombre de comparaisons (le nombre de déplacements reste O(n) cependant).

✅ Réponse 4.3

import bisect

def insertion_sort_binaire(liste):
for i in range(1, len(liste)):
cle = liste[i]
# recherche binaire de la position d'insertion dans liste[0:i]
pos = bisect.bisect_left(liste, cle, 0, i)
# décaler les éléments pour libérer la place
liste[pos + 1:i + 1] = liste[pos:i]
liste[pos] = cle
return liste

print(insertion_sort_binaire([12, 11, 13, 5, 6]))

# [5, 6, 11, 12, 13]

☑ À la fin de ce module, vous devez savoir implémenter le tri par insertion classique et sa variante binaire, et expliquer
pourquoi ce tri est très performant sur des données presque triées.

Page 9 / 22
 Module 5 — Tri fusion (Merge Sort)

Durée : 4h Complexité : O(n log n) Stable · Diviser pour régner

Résumé de la leçon
Le tri fusion applique le paradigme "diviser pour régner" : on divise récursivement la liste en deux moitiés jusqu'à
obtenir des sous-listes d'un seul élément (donc triées par définition), puis on fusionne ces sous-listes deux à deux en les
remettant dans l'ordre. C'est l'un des algorithmes de tri les plus fiables, avec une complexité garantie de O(n log n) dans
tous les cas, mais il nécessite de la mémoire supplémentaire (O(n)).

Meilleur cas Cas moyen Pire cas Mémoire

O(n log n) O(n log n) O(n log n) O(n)

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

def fusionner(gauche, droite):

resultat = []
i = j = 0
while i < len(gauche) and j < len(droite):
if gauche[i] <= droite[j]:
[Link](gauche[i]); i += 1
else:
[Link](droite[j]); j += 1
[Link](gauche[i:])
[Link](droite[j:])
return resultat

✏️Exercices

Exercice 5.1 — Implémentation de base

Implémentez le tri fusion complet (fonctions merge_sort et fusionner ) et testez-le sur [38, 27, 43, 3, 9, 82,
10] .

✅ Réponse 5.1

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

def fusionner(gauche, droite):

resultat = []
i = j = 0
while i < len(gauche) and j < len(droite):
if gauche[i] <= droite[j]:
[Link](gauche[i]); i += 1
else:
[Link](droite[j]); j += 1
[Link](gauche[i:])
[Link](droite[j:])
return resultat

print(merge_sort([38, 27, 43, 3, 9, 82, 10]))

# [3, 9, 10, 27, 38, 43, 82]

Page 10 / 22
Exercice 5.2 — Compter les inversions
Le nombre d'inversions d'une liste est le nombre de paires (i, j) telles que i < j mais liste[i] > liste[j]. En utilisant
une variante du tri fusion (l'étape de fusion compte les inversions), écrivez une fonction
compter_inversions(liste) qui retourne ce nombre en O(n log n).

✅ Réponse 5.2

def compter_inversions(liste):
_, nb = _tri_et_compte(liste)
return nb

def _tri_et_compte(liste):
if len(liste) <= 1:
return liste, 0
milieu = len(liste) // 2
gauche, inv_g = _tri_et_compte(liste[:milieu])
droite, inv_d = _tri_et_compte(liste[milieu:])
fusion, inv_f = _fusionner_compte(gauche, droite)
return fusion, inv_g + inv_d + inv_f

def _fusionner_compte(gauche, droite):

resultat = []
i = j = 0
inversions = 0
while i < len(gauche) and j < len(droite):
if gauche[i] <= droite[j]:
[Link](gauche[i]); i += 1
else:
# tous les éléments restants de "gauche" forment une inversion avec droite[j]
[Link](droite[j]); j += 1
inversions += len(gauche) - i
[Link](gauche[i:])
[Link](droite[j:])
return resultat, inversions

print(compter_inversions([2, 4, 1, 3, 5]))
# 3 (paires (2,1), (4,1), (4,3))

Exercice 5.3 — Fusionner k listes triées

Écrivez une fonction fusionner_k_listes(listes) qui prend une liste de k listes déjà triées et retourne une seule
liste triée, en réutilisant la fonction fusionner (fusion deux à deux, façon "tournoi").

✅ Réponse 5.3

def fusionner(gauche, droite):

resultat = []
i = j = 0
while i < len(gauche) and j < len(droite):
if gauche[i] <= droite[j]:
[Link](gauche[i]); i += 1
else:
[Link](droite[j]); j += 1
[Link](gauche[i:])
[Link](droite[j:])
return resultat

def fusionner_k_listes(listes):
if not listes:
return []
while len(listes) > 1:
listes_fusionnees = []
for i in range(0, len(listes), 2):
if i + 1 < len(listes):
listes_fusionnees.append(fusionner(listes[i], listes[i + 1]))
else:
listes_fusionnees.append(listes[i])
listes = listes_fusionnees
return listes[0]

Page 11 / 22
 print(fusionner_k_listes([[1, 4, 7], [2, 5], [0, 3, 6, 9]]))
# [0, 1, 2, 3, 4, 5, 6, 7, 9]

☑ À la fin de ce module, vous devez maîtriser le paradigme "diviser pour régner", implémenter le tri fusion, et l'adapter
pour compter des inversions ou fusionner plusieurs listes triées.

Page 12 / 22
 Module 6 — Tri rapide (Quick Sort)

Durée : 4h Complexité : O(n log n) moyen / O(n²) pire cas Instable · En place

Résumé de la leçon
Le tri rapide choisit un élément pivot, puis partitionne la liste en deux groupes : les éléments plus petits que le pivot et
ceux plus grands. Il trie ensuite récursivement chaque groupe. C'est l'un des tris les plus rapides en pratique grâce à sa
bonne localité mémoire, mais son pire cas (O(n²)) survient quand le pivot est mal choisi (ex : toujours le premier élément
sur une liste déjà triée).

Meilleur cas Cas moyen Pire cas Mémoire

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

def quick_sort(liste):
if len(liste) <= 1:
return liste
pivot = liste[len(liste) // 2]
plus_petits = [x for x in liste if x < pivot]
egaux = [x for x in liste if x == pivot]
plus_grands = [x for x in liste if x > pivot]
return quick_sort(plus_petits) + egaux + quick_sort(plus_grands)

✏️Exercices

Exercice 6.1 — Implémentation simple

Implémentez le tri rapide (version simple par compréhensions de liste) et testez-le sur [10, 7, 8, 9, 1, 5] .

✅ Réponse 6.1

def quick_sort(liste):
if len(liste) <= 1:
return liste
pivot = liste[len(liste) // 2]
plus_petits = [x for x in liste if x < pivot]
egaux = [x for x in liste if x == pivot]
plus_grands = [x for x in liste if x > pivot]
return quick_sort(plus_petits) + egaux + quick_sort(plus_grands)

print(quick_sort([10, 7, 8, 9, 1, 5]))
# [1, 5, 7, 8, 9, 10]

Exercice 6.2 — Tri rapide en place (partition de Lomuto)

Implémentez le tri rapide "en place" (sans créer de nouvelles listes), en utilisant le schéma de partition de Lomuto,
qui échange les éléments directement dans la liste d'origine.

✅ Réponse 6.2

def quick_sort_en_place(liste, bas=0, haut=None):

if haut is None:
haut = len(liste) - 1
if bas < haut:
pos_pivot = partition_lomuto(liste, bas, haut)
quick_sort_en_place(liste, bas, pos_pivot - 1)
quick_sort_en_place(liste, pos_pivot + 1, haut)
return liste

def partition_lomuto(liste, bas, haut):

pivot = liste[haut]
i = bas - 1
for j in range(bas, haut):

Page 13 / 22
 if liste[j] <= pivot:
i += 1
liste[i], liste[j] = liste[j], liste[i]
liste[i + 1], liste[haut] = liste[haut], liste[i + 1]
return i + 1

print(quick_sort_en_place([10, 7, 8, 9, 1, 5]))
# [1, 5, 7, 8, 9, 10]

Exercice 6.3 — Choix aléatoire du pivot

Le pire cas O(n²) survient souvent avec un mauvais choix de pivot sur des données déjà triées. Modifiez le tri rapide
en place pour choisir un pivot aléatoire à chaque partition, ce qui rend le pire cas beaucoup moins probable.

✅ Réponse 6.3

import random

def quick_sort_aleatoire(liste, bas=0, haut=None):

if haut is None:
haut = len(liste) - 1
if bas < haut:
pos_pivot = partition_aleatoire(liste, bas, haut)
quick_sort_aleatoire(liste, bas, pos_pivot - 1)
quick_sort_aleatoire(liste, pos_pivot + 1, haut)
return liste

def partition_aleatoire(liste, bas, haut):

indice_alea = [Link](bas, haut)
liste[indice_alea], liste[haut] = liste[haut], liste[indice_alea]
pivot = liste[haut]
i = bas - 1
for j in range(bas, haut):
if liste[j] <= pivot:
i += 1
liste[i], liste[j] = liste[j], liste[i]
liste[i + 1], liste[haut] = liste[haut], liste[i + 1]
return i + 1

# Testé sur une liste déjà triée (pire cas classique) :

print(quick_sort_aleatoire([1, 2, 3, 4, 5, 6, 7, 8]))
# [1, 2, 3, 4, 5, 6, 7, 8]

☑ À la fin de ce module, vous devez comprendre le mécanisme de partition, savoir implémenter le tri rapide en place, et
connaître les techniques (pivot aléatoire, médiane de trois) pour éviter le pire cas.

Page 14 / 22
 Module 7 — Tri par tas (Heap Sort)

Durée : 3h Complexité : O(n log n) Instable · En place

Résumé de la leçon
Le tri par tas utilise une structure de données appelée tas binaire max (max-heap) : un arbre binaire presque complet
où chaque parent est plus grand que ses enfants. On construit d'abord le tas à partir de la liste, puis on extrait
répétitivement le maximum (la racine) qu'on place à la fin de la liste, en réajustant le tas à chaque extraction.
Contrairement au tri fusion, il ne nécessite pas de mémoire supplémentaire.

Meilleur cas Cas moyen Pire cas Mémoire

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

def heap_sort(liste):
n = len(liste)
for i in range(n // 2 - 1, -1, -1):
entasser(liste, n, i)
for i in range(n - 1, 0, -1):
liste[0], liste[i] = liste[i], liste[0]
entasser(liste, i, 0)
return liste

def entasser(liste, n, i):

plus_grand = i
gauche, droite = 2 * i + 1, 2 * i + 2
if gauche < n and liste[gauche] > liste[plus_grand]:
plus_grand = gauche
if droite < n and liste[droite] > liste[plus_grand]:
plus_grand = droite
if plus_grand != i:
liste[i], liste[plus_grand] = liste[plus_grand], liste[i]
entasser(liste, n, plus_grand)

✏️Exercices

Exercice 7.1 — Implémentation de base

Implémentez le tri par tas complet et testez-le sur [12, 11, 13, 5, 6, 7] .

✅ Réponse 7.1

def entasser(liste, n, i):

plus_grand = i
gauche, droite = 2 * i + 1, 2 * i + 2
if gauche < n and liste[gauche] > liste[plus_grand]:
plus_grand = gauche
if droite < n and liste[droite] > liste[plus_grand]:
plus_grand = droite
if plus_grand != i:
liste[i], liste[plus_grand] = liste[plus_grand], liste[i]
entasser(liste, n, plus_grand)

def heap_sort(liste):
n = len(liste)
for i in range(n // 2 - 1, -1, -1):
entasser(liste, n, i)
for i in range(n - 1, 0, -1):
liste[0], liste[i] = liste[i], liste[0]
entasser(liste, i, 0)
return liste

print(heap_sort([12, 11, 13, 5, 6, 7]))

# [5, 6, 7, 11, 12, 13]

Page 15 / 22
Exercice 7.2 — File de priorité avec heapq
Utilisez le module standard heapq pour implémenter une file de priorité qui retourne toujours les 3 plus petits
éléments d'une liste, sans trier la liste entière.

✅ Réponse 7.2

import heapq

def trois_plus_petits(liste):
return [Link](3, liste)

liste = [12, 11, 13, 5, 6, 7, 1, 9]

print(trois_plus_petits(liste))
# [1, 5, 6]

# Équivalent manuel avec un tas :

def trois_plus_petits_manuel(liste):
tas = liste[:]
[Link](tas) # O(n)
return [[Link](tas) for _ in range(3)] # O(k log n)

print(trois_plus_petits_manuel(liste))
# [1, 5, 6]

Exercice 7.3 — Vérifier la propriété de tas

Écrivez une fonction est_un_max_heap(liste) qui vérifie si une liste représente bien un tas max valide (chaque
parent ≥ ses enfants).

✅ Réponse 7.3

def est_un_max_heap(liste):
n = len(liste)
for i in range(n):
gauche, droite = 2 * i + 1, 2 * i + 2
if gauche < n and liste[i] < liste[gauche]:
return False
if droite < n and liste[i] < liste[droite]:
return False
return True

print(est_un_max_heap([13, 11, 12, 5, 6, 7])) # True

print(est_un_max_heap([1, 2, 3, 4, 5, 6])) # False

☑ À la fin de ce module, vous devez comprendre la structure de tas binaire, savoir implémenter entasser et
heap_sort , et connaître le module heapq de Python.

Page 16 / 22
 Module 8 — Tri par comptage et Tri par base (Counting /
Radix Sort)

Durée : 3h Complexité : O(n + k) Tris non comparatifs

Résumé de la leçon
Contrairement aux tris précédents, le tri par comptage (Counting Sort) et le tri par base (Radix Sort) ne comparent
pas les éléments entre eux : ils exploitent la structure des données (nombres entiers dans un intervalle connu). Le tri par
comptage compte les occurrences de chaque valeur puis reconstruit la liste triée. Le tri par base applique un tri par
comptage sur chaque chiffre (unités, dizaines, ...), du moins significatif au plus significatif. Ces algorithmes peuvent
battre la limite théorique O(n log n) des tris comparatifs, mais uniquement sous des conditions particulières.

Algorithme Complexité Mémoire Condition

Counting Sort O(n + k) O(n + k) k = étendue des valeurs, doit être raisonnable

Radix Sort O(d·(n + b)) O(n + b) d = nb de chiffres, b = base (souvent 10)

def counting_sort(liste):
if not liste:
return liste
maxi = max(liste)
compteur = [0] * (maxi + 1)
for x in liste:
compteur[x] += 1
resultat = []
for valeur, occurrences in enumerate(compteur):
[Link]([valeur] * occurrences)
return resultat

✏️Exercices

Exercice 8.1 — Tri par comptage

Implémentez le tri par comptage et testez-le sur [4, 2, 2, 8, 3, 3, 1] .

✅ Réponse 8.1

def counting_sort(liste):
if not liste:
return liste
maxi = max(liste)
compteur = [0] * (maxi + 1)
for x in liste:
compteur[x] += 1
resultat = []
for valeur, occurrences in enumerate(compteur):
[Link]([valeur] * occurrences)
return resultat

print(counting_sort([4, 2, 2, 8, 3, 3, 1]))
# [1, 2, 2, 3, 3, 4, 8]

Exercice 8.2 — Tri par comptage stable (avec tableau de sortie)

La version précédente ne fonctionne que sur des entiers et n'est pas "stable" au sens strict (elle ne conserve pas
d'objets associés). Implémentez une version stable du tri par comptage, qui place chaque élément directement
dans un tableau de sortie à sa position calculée à partir des sommes cumulées.

✅ Réponse 8.2

Page 17 / 22
 def counting_sort_stable(liste):
if not liste:
return liste
maxi = max(liste)
compteur = [0] * (maxi + 1)
for x in liste:
compteur[x] += 1
# sommes cumulées : compteur[v] = nombre d'éléments <= v
for v in range(1, maxi + 1):
compteur[v] += compteur[v - 1]
sortie = [0] * len(liste)
# parcours de droite à gauche pour garantir la stabilité
for x in reversed(liste):
compteur[x] -= 1
sortie[compteur[x]] = x
return sortie

print(counting_sort_stable([4, 2, 2, 8, 3, 3, 1]))
# [1, 2, 2, 3, 3, 4, 8]

Exercice 8.3 — Tri par base (Radix Sort)

Implémentez le tri par base (LSD Radix Sort) pour trier une liste d'entiers positifs, en réutilisant le tri par comptage
stable chiffre par chiffre. Testez-le sur [170, 45, 75, 90, 802, 24, 2, 66] .

✅ Réponse 8.3

def counting_sort_par_chiffre(liste, exp):

n = len(liste)
sortie = [0] * n
compteur = [0] * 10
for x in liste:
chiffre = (x // exp) % 10
compteur[chiffre] += 1
for i in range(1, 10):
compteur[i] += compteur[i - 1]
for x in reversed(liste):
chiffre = (x // exp) % 10
compteur[chiffre] -= 1
sortie[compteur[chiffre]] = x
return sortie

def radix_sort(liste):
if not liste:
return liste
maxi = max(liste)
exp = 1
while maxi // exp > 0:
liste = counting_sort_par_chiffre(liste, exp)
exp *= 10
return liste

print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))

# [2, 24, 45, 66, 75, 90, 170, 802]

☑ À la fin de ce module, vous devez comprendre pourquoi les tris non comparatifs peuvent dépasser la limite O(n log n),
et savoir dans quels cas les utiliser (petits entiers, étendue de valeurs limitée).

Page 18 / 22
 Module 9 — Synthèse, comparaison et projet final

Durée : 2h Révision générale Mini-projet

Résumé de la leçon
Ce dernier module consolide tout ce qui a été appris. Voici un tableau récapitulatif des algorithmes étudiés :

Algorithme Meilleur Moyen Pire Mémoire Stable

Bulles O(n) O(n²) O(n²) O(1) Oui

Sélection O(n²) O(n²) O(n²) O(1) Non

Insertion O(n) O(n²) O(n²) O(1) Oui

Fusion O(n log n) O(n log n) O(n log n) O(n) Oui

Rapide O(n log n) O(n log n) O(n²) O(log n) Non

Tas O(n log n) O(n log n) O(n log n) O(1) Non

Comptage O(n+k) O(n+k) O(n+k) O(n+k) Oui

Base (Radix) O(d(n+b)) O(d(n+b)) O(d(n+b)) O(n+b) Oui

En pratique : privilégiez insertion sort pour de très petites listes, quick sort pour la vitesse générale (c'est ce qu'utilise
sorted() / Timsort combiné à l'insertion en interne côté Python — Timsort mélange fusion et insertion), et merge sort
ou heap sort quand une complexité garantie O(n log n) est nécessaire.

✏️Exercices

Exercice 9.1 — Benchmark comparatif

Écrivez un script qui compare le temps d'exécution de bubble_sort , merge_sort , quick_sort et sorted() (natif)
sur une liste aléatoire de 2000 éléments.

✅ Réponse 9.1

import random
import time

def chronometrer(fonction, liste):

copie = [Link]()
debut = time.perf_counter()
fonction(copie)
return time.perf_counter() - debut

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

def merge_sort(liste):
if len(liste) <= 1:
return liste
m = len(liste) // 2
g, d = merge_sort(liste[:m]), merge_sort(liste[m:])
resultat, i, j = [], 0, 0
while i < len(g) and j < len(d):
if g[i] <= d[j]:
[Link](g[i]); i += 1
else:
[Link](d[j]); j += 1
return resultat + g[i:] + d[j:]

Page 19 / 22
 def quick_sort(liste):
if len(liste) <= 1:
return liste
pivot = liste[len(liste) // 2]
return (quick_sort([x for x in liste if x < pivot])
+ [x for x in liste if x == pivot]
+ quick_sort([x for x in liste if x > pivot]))

liste = [Link](range(1_000_000), 2000)

print("Bulles :", chronometrer(bubble_sort, liste), "s")

print("Fusion :", chronometrer(merge_sort, liste), "s")
print("Rapide :", chronometrer(quick_sort, liste), "s")
print("sorted():", chronometrer(sorted, liste), "s")
# sorted() (Timsort) est généralement le plus rapide,
# suivi de quick_sort et merge_sort, puis bubble_sort loin derrière.

Exercice 9.2 — Choisir le bon algorithme

Pour chacun des scénarios suivants, indiquez et justifiez en une phrase l'algorithme de tri le plus adapté : (a) trier
50 notes d'élèves entières entre 0 et 20 ; (b) trier une liste presque déjà triée de 10 000 éléments ; (c) trier 10
millions d'éléments avec une garantie stricte de performance.

✅ Réponse 9.2

# (a) 50 notes entre 0 et 20 :

# -> Counting Sort : k=20 est petit, complexité O(n+k) quasi O(n).
def counting_sort(liste, maxi=20):
compteur = [0] * (maxi + 1)
for x in liste:
compteur[x] += 1
resultat = []
for valeur, occ in enumerate(compteur):
[Link]([valeur] * occ)
return resultat

# (b) liste presque triée de 10 000 éléments :

# -> Insertion Sort : proche de O(n) sur des données presque triées,
# contrairement à sélection ou tri rapide non adaptés à ce cas.

# (c) 10 millions d'éléments, garantie stricte :

# -> Merge Sort ou Heap Sort : tous deux garantissent O(n log n)
# même dans le pire cas, contrairement à Quick Sort (O(n²) possible).

Exercice 9.3 — Projet final : trieur générique

Créez une fonction trier(liste, methode="rapide") qui accepte un paramètre methode ( "bulles" ,
"insertion" , "fusion" , "rapide" , "tas" ) et applique l'algorithme correspondant. Ajoutez une gestion d'erreur
si la méthode n'existe pas.

✅ Réponse 9.3

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

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

Page 20 / 22
 liste[j + 1] = cle
return liste

def merge_sort(liste):
if len(liste) <= 1:
return liste
m = len(liste) // 2
g, d = merge_sort(liste[:m]), merge_sort(liste[m:])
resultat, i, j = [], 0, 0
while i < len(g) and j < len(d):
if g[i] <= d[j]:
[Link](g[i]); i += 1
else:
[Link](d[j]); j += 1
return resultat + g[i:] + d[j:]

def quick_sort(liste):
if len(liste) <= 1:
return liste
pivot = liste[len(liste) // 2]
return (quick_sort([x for x in liste if x < pivot])
+ [x for x in liste if x == pivot]
+ quick_sort([x for x in liste if x > pivot]))

def heap_sort(liste):
liste = [Link]()
def entasser(l, n, i):
plus_grand = i
g, d = 2 * i + 1, 2 * i + 2
if g < n and l[g] > l[plus_grand]: plus_grand = g
if d < n and l[d] > l[plus_grand]: plus_grand = d
if plus_grand != i:
l[i], l[plus_grand] = l[plus_grand], l[i]
entasser(l, n, plus_grand)
n = len(liste)
for i in range(n // 2 - 1, -1, -1):
entasser(liste, n, i)
for i in range(n - 1, 0, -1):
liste[0], liste[i] = liste[i], liste[0]
entasser(liste, i, 0)
return liste

def trier(liste, methode="rapide"):

methodes = {
"bulles": bubble_sort,
"insertion": insertion_sort,
"fusion": merge_sort,
"rapide": quick_sort,
"tas": heap_sort,
}
if methode not in methodes:
raise ValueError(
f"Méthode inconnue : '{methode}'. Choix possibles : {list([Link]())}"
)
return methodes[methode](liste)

print(trier([5, 3, 8, 1, 9], methode="fusion"))

# [1, 3, 5, 8, 9]
print(trier([5, 3, 8, 1, 9], methode="tas"))
# [1, 3, 5, 8, 9]

☑ Félicitations ! Vous avez maintenant une vue d'ensemble complète des algorithmes de tri classiques, leur complexité,
leurs cas d'usage, et vous savez les implémenter en Python.

Page 21 / 22
🎓 Fin du programme — 24 heures
Ce plan couvre les algorithmes de tri fondamentaux (comparatifs et non comparatifs) attendus dans toute
formation en algorithmique ou en entretien technique. Pour aller plus loin : étudiez Timsort (l'algorithme utilisé par
Python en interne), le tri par bucket (Bucket Sort), et les tris parallèles/externes pour les très grands volumes de
données ne tenant pas en mémoire.

Page 22 / 22