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)
- **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
Thème complet
Voir tous les chapitres « Algorithmique et programmation » de la Seconde à la Terminale
Ce thème dans une autre classe
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)$.