NSI (Spé) — Algorithmique
Tri par sélection et tri par insertion
Algorithmes de tri élémentaires : principe, implémentation, complexité
Résumé synthétiqueFiche en 4 sectionsQuiz de 10 questionsGratuit, sans pub
Résumé
Les algorithmes de tri ordonnent les éléments d'une liste selon un critère. Le tri par sélection cherche le minimum de la partie non triée, le place au début, puis recommence. Le tri par insertion traite les éléments un par un et insère chacun à sa place dans la partie déjà triée, comme on range des cartes dans sa main. Ces deux tris ont une complexité quadratique $O(n^2)$ dans le pire cas, ce qui les rend lents sur de grandes listes. Le tri par insertion est cependant rapide quand la liste est presque triée. Prouver qu'un tri est correct repose sur un invariant de boucle : une propriété vraie à chaque itération.
Le tri par sélection est le plus intuitif : à chaque étape, on cherche le plus petit élément restant et on le met à sa place définitive. La liste se construit triée de gauche à droite, un minimum après l'autre.
![Tri par sélection de [5, 3, 8, 1] : à chaque étape on extrait le minimum et on le place à gauche, jusqu'à la liste triée](/fiches/pre-nsi-9-tri-selection.svg)
À chaque étape, le minimum de la partie non triée (en vert) est amené à sa place définitive.
- Principe : chercher le minimum de la partie non triée et l'amener au début de celle-ci.
- Déroulé : placer le min en position 0, puis le min du reste en position 1, etc.
- Implémentation : deux boucles imbriquées (i de 0 à n-2, j de i+1 à n-1).
- Échange : t[i], t[j_min] = t[j_min], t[i] (affectation simultanée en Python).
- Comparaisons : toujours $n(n-1)/2$, quel que soit l'état initial, soit $O(n^2)$.
Exemple
Sur [5, 3, 8, 1] : on trouve le min 1, on l'échange avec 5 → [1, 3, 8, 5]. Min du reste : 3, déjà placé. Min suivant : 5, échangé avec 8 → [1, 3, 5, 8]. Trié.
Piège à éviter
Le tri par sélection fait toujours $n(n-1)/2$ comparaisons, même sur une liste déjà triée : il ne profite jamais d'un ordre initial favorable, contrairement au tri par insertion.
Le tri par insertion imite le rangement de cartes dans la main : on prend chaque nouvel élément et on le glisse à sa place parmi ceux déjà triés, en décalant les plus grands. C'est un tri qui s'accélère beaucoup quand la liste est presque en ordre.
- Principe : insérer chaque élément à sa place dans la partie gauche déjà triée.
- Analogie : comme trier des cartes en glissant chaque nouvelle carte au bon endroit.
- Départ : on commence à l'indice 1 (l'élément 0 est déjà « trié » seul).
- Décalage : on compare aux précédents et on décale les plus grands vers la droite.
- Meilleur cas : liste déjà triée → $O(n)$ ; pire cas : ordre inverse → $O(n^2)$.
Exemple
Sur [5, 3, 8, 1] : 3 s'insère avant 5 → [3, 5, 8, 1] ; 8 reste en place → [3, 5, 8, 1] ; 1 remonte tout au début → [1, 3, 5, 8].
Piège à éviter
Pour une liste déjà triée, le tri par insertion ne fait aucun décalage et coûte seulement $O(n)$. C'est sa force face au tri par sélection, qui reste à $O(n^2)$ dans tous les cas.
La complexité en temps mesure le nombre d'opérations selon la taille n de l'entrée. Elle permet de comparer les algorithmes sans dépendre de la machine. Pour les tris, elle explique pourquoi on abandonne ces méthodes élémentaires sur de grands volumes.
- Définition : la complexité compte les opérations en fonction de la taille n.
- Pire cas commun : les deux tris sont en $O(n^2)$ (quadratique).
- Sélection : toujours $n(n-1)/2$ comparaisons, peu d'échanges.
- Insertion : quasi-linéaire si la liste est presque triée.
- Au-delà : pour de grandes listes, on préfère un tri en $O(n \log n)$ comme le tri fusion.
Exemple
Sur une liste de 10 éléments, le tri par sélection fait $\dfrac{10 \times 9}{2} = 45$ comparaisons. Sur un million d'éléments, $O(n^2)$ donnerait mille milliards d'opérations : impraticable.
Piège à éviter
En Python, on n'écrit pas ces tris en pratique : sorted() et .sort() utilisent Timsort, un algorithme hybride en $O(n \log n)$, bien plus rapide. Les tris élémentaires servent surtout à comprendre la complexité.
Comment être sûr qu'un tri fonctionne, sans le tester sur tous les cas ? On exhibe un invariant de boucle : une propriété vraie à chaque tour. En montrant son initialisation, sa conservation et la terminaison, on prouve la correction de l'algorithme.
- Invariant : une propriété vraie avant et après chaque itération.
- Initialisation : l'invariant est vrai avant le premier tour de boucle.
- Conservation : s'il est vrai avant un tour, il l'est encore après.
- Terminaison : la boucle finit, et l'invariant final donne le résultat attendu.
- Exemple (sélection) : après l'étape i, les i+1 premiers éléments sont les plus petits, triés.
Exemple
Pour le tri par insertion, l'invariant est : « après l'itération i, les éléments d'indices 0 à i sont triés entre eux ». À la fin (i = n-1), toute la liste est donc triée.
Piège à éviter
Un invariant doit être vrai à chaque itération, pas seulement à la fin : si l'on ne vérifie pas la conservation à chaque tour, la « preuve » ne garantit rien sur le résultat final.
Quiz - Tri par sélection et tri par insertion
10 questions
S'entraîner
Thème complet
Voir tous les chapitres « Algorithmique et programmation » de la Seconde à la Terminale
Ce thème dans une autre classe
Articles utiles
Questions fréquentes
Les points clés à retenir sur Tri par sélection et tri par insertion, extraits du quiz de révision.
Quel est le principe du tri par sélection ?
Réponse :
Chercher le minimum et le placer au début
Le tri par sélection cherche le minimum de la partie non triée et l'amène à sa place, étape par étape.
Quelle est la complexité du tri par sélection dans le pire cas ?
Réponse :
$O(n^2)$
Il fait toujours $n(n-1)/2$ comparaisons, soit une complexité $O(n^2)$.
Quelle analogie décrit le mieux le tri par insertion ?
Réponse :
Trier des cartes dans sa main
Le tri par insertion fonctionne comme quand on glisse chaque carte à sa place parmi celles déjà triées.
Quel est le meilleur cas du tri par insertion ?
Réponse :
Liste déjà triée
Sur une liste déjà triée, aucun décalage n'est nécessaire : la complexité tombe à $O(n)$.