Introduction
Trier une liste signifie organiser ses éléments selon un ordre donné, généralement croissant ou décroissant. Cette opération est au cœur de nombreux algorithmes informatiques. Elle permet de simplifier ou d’optimiser des tâches comme la recherche, l’analyse de données ou la détection de doublons. Dans cette leçon, deux méthodes classiques sont étudiées : le tri par insertion et le tri par sélection. Ces algorithmes illustrent des raisonnements fondamentaux sur la correction, les invariants, la terminaison et l’analyse de la complexité.
Le tri par insertion
Le tri par insertion consiste à construire progressivement une liste triée en insérant un à un les éléments à leur bonne position.
Principe
On commence avec une sous-liste contenant uniquement le premier élément, considérée comme triée. Ensuite, on prend chaque nouvel élément et on le place à sa bonne position dans la partie déjà triée, en décalant les autres éléments si besoin.
Exemple avec la liste [5, 2, 4, 1] :
Étape 1 : [5] | 2, 4, 1.
Étape 2 : [2, 5] | 4, 1.
Étape 3 : [2, 4, 5] | 1.
Étape 4 : [1, 2, 4, 5].
Implémentation en Python
def tri_insertion(L):
for i in range(1, len(L)):
valeur = L[i]
j = i - 1
while j >= 0 and L[j] > valeur:
L[j + 1] = L[j]
j -= 1
L[j + 1] = valeur
Invariant
L’invariant de boucle est que les i premiers éléments de la liste sont toujours triés au début de chaque itération. Cet invariant permet de prouver la correction de l’algorithme.
Terminaison
La terminaison est garantie car la valeur de i augmente strictement à chaque tour de boucle principale, et que la boucle interne while décale les éléments vers la droite jusqu’à trouver la position correcte pour l’insertion.
Complexité
Dans le pire des cas (liste inversée), chaque insertion nécessite de comparer et décaler presque tous les éléments précédents. Il y a donc environ n² comparaisons et déplacements : le coût est quadratique (O(n²)).
À retenir
Le tri par insertion insère chaque élément à sa place dans une sous-liste déjà triée. Il repose sur un invariant clair, se termine toujours, et a un coût quadratique dans le pire des cas.
Le tri par sélection
Le tri par sélection repose sur un principe différent : à chaque étape, on cherche le plus petit élément restant et on le place à sa position définitive.
Principe
On parcourt la liste pour trouver le plus petit élément, qu’on échange avec l’élément à la première position. Ensuite, on recommence avec le reste de la liste.
Exemple avec la liste [5, 2, 4, 1] :
Étape 1 : on échange 5 et 1 → [1] | 2, 4, 5.
Étape 2 : on échange 2 et 2 → [1, 2] | 4, 5.
Étape 3 : on échange 4 et 4 → [1, 2, 4] | 5.
Étape 4 : [1, 2, 4, 5].
Remarque : parfois l’échange est sans effet visible, mais il est tout de même effectué.
Implémentation en Python
def tri_selection(L):
n = len(L)
for i in range(n):
indice_min = i
for j in range(i + 1, n):
if L[j] < L[indice_min]:
indice_min = j
L[i], L[indice_min] = L[indice_min], L[i]
Invariant
L’invariant est que les i premiers éléments sont toujours les plus petits de la liste et sont triés. À chaque itération, le plus petit des éléments restants est mis à sa place définitive.
Terminaison
La boucle principale augmente strictement l’indice i, et le nombre d’éléments à traiter diminue à chaque étape : cela garantit la terminaison de l’algorithme.
Complexité
L’algorithme effectue toujours le même nombre de comparaisons, peu importe l’ordre initial : il parcourt chaque sous-liste restante pour trouver le minimum. Le coût est quadratique (O(n²)), avec un nombre d’échanges généralement plus faible que le tri par insertion.
À retenir
Le tri par sélection place successivement les plus petits éléments à leur bonne position. Il utilise un invariant simple, se termine toujours et a un coût quadratique.
Comparaison des deux tris
Les tris par insertion et par sélection présentent des similarités (coût quadratique, structure en double boucle) mais diffèrent dans leur comportement :
Le tri par insertion est plus efficace sur les listes presque triées, car il effectue peu de déplacements.
Le tri par sélection effectue un nombre constant de comparaisons, mais peut faire des échanges inutiles.
Tous deux sont faciles à implémenter et très utiles pour introduire les notions d’invariant, de preuve de terminaison, et d’analyse de la complexité.
Conclusion
Les tris par insertion et sélection sont deux méthodes classiques pour ordonner les éléments d’une liste. Ils illustrent les grands principes de l’algorithmique : raisonnement par étapes, utilisation d’invariants, preuve de terminaison et estimation du coût. Bien que leur complexité quadratique les rende peu efficaces pour de grandes quantités de données, ils constituent une excellente base pour comprendre des algorithmes plus avancés, qui seront étudiés en terminale.