Les tris
Cours · informatique (tronc commun des prépas scientifiques), chapitre 9 · prépas scientifiques, tronc commun · le début du chapitre, la suite sur Adloun
9.1 Introduction et motivation
Trier — ranger des données selon un ordre — est l'opération la plus étudiée de l'histoire de l'informatique, et pour cause : une donnée triée change de nature. La recherche y devient dichotomique (chapitre 5), les doublons s'y touchent, la médiane s'y lit (chapitre 4), la paire la plus proche y est voisine (chapitre 3) — trier d'abord est le premier réflexe de simplification d'une foule de problèmes.
Ce chapitre rassemble les grands algorithmes de tri et, surtout, leur zoologie : aux deux tris quadratiques fondamentaux — sélection et insertion — succèdent le tri par partition-fusion et le tri rapide, qui brisent le mur du pour atteindre , puis le tri par comptage qui, en trichant avec les comparaisons, descend à . Chaque algorithme se décrit par ses caractéristiques — stable ou non, en place ou non, comparatif ou non — qui décident de son emploi bien plus que sa seule complexité. Et le chapitre se ferme sur un théorème remarquable : n'est pas un exploit mais une frontière — aucun tri par comparaisons ne fera jamais mieux.
9.2 Le problème du tri
Trier le tableau , c'est produire un tableau tel que :
- est croissant : pour tout ;
- est une permutation de : mêmes éléments, avec les mêmes multiplicités.
Les deux clauses sont indispensables — le chapitre 3 a montré qu'oublier la seconde laisse passer des tris qui « perdent » des éléments.
- Un tri est en place s'il réordonne le tableau dans sa propre mémoire (quelques variables auxiliaires au plus), sans tableau annexe de taille comparable.
- Un tri est stable si deux éléments égaux (au sens de la clé de tri) restent dans leur ordre relatif initial — crucial pour trier des fiches : trier par note des élèves déjà rangés par nom conserve, à note égale, l'ordre alphabétique.
- Un tri est comparatif s'il n'accède aux éléments que par comparaisons () — sans regarder leur valeur. Tous les tris du chapitre le sont, sauf le dernier.
9.3 Le tri par sélection
À chaque étape, sélectionner le minimum de la partie non triée et le placer juste après la partie triée :
def tri_selection(t: list) -> None:
"""Trie t en place."""
n = len(t)
for i in range(n - 1):
# Invariant : t[0..i-1] est trié et contient les i plus petits éléments
imin = i
for j in range(i + 1, n):
if t[j] < t[imin]:
imin = j
t[i], t[imin] = t[imin], t[i]Démonstration (Correction)
Invariant : « est trié et ses éléments sont inférieurs ou égaux à tous ceux de ». Initialisation : préfixe vide. Conservation : la boucle interne calcule l'indice du minimum de (invariant du chapitre 2) ; l'échange place ce minimum en position — il majore le préfixe (par ) et minore le reste : . À la sortie (), le préfixe est trié et minore : tout est trié, et l'on n'a fait qu'échanger des éléments de — permutation garantie.
Complexité : Tri par sélection
La boucle interne fait comparaisons : total , quel que soit le tableau — déjà trié ou non, la sélection ne voit rien. En revanche, au plus échanges : c'est le tri qui écrit le moins, précieux quand l'écriture coûte cher. Non stable dans cette version : l'échange peut faire sauter un élément par-dessus son égal.
9.4 Le tri par insertion
Le tri du joueur de cartes : prendre les éléments un à un et insérer chacun à sa place dans la partie déjà triée, en décalant les plus grands vers la droite :
def tri_insertion(t: list) -> None:
"""Trie t en place."""
for i in range(1, len(t)):
# Invariant : t[0..i-1] est trié (mêmes éléments qu'au départ)
x = t[i]
j = i
while j > 0 and t[j - 1] > x:
t[j] = t[j - 1] # décaler vers la droite
j -= 1
t[j] = x # insérer x dans le trou