Introduction : Pourquoi apprendre à trier ?
Dans le monde de l'informatique, les données sont souvent en désordre. Pourtant, pour les analyser, les rechercher ou les présenter, nous avons besoin qu'elles soient organisées. Trier une liste, c'est l'arranger dans un ordre croissant ou décroissant. C'est une opération tellement fondamentale qu'elle a donné naissance à toute une famille d'algorithmes de tri. En NSI, tu dois maîtriser les plus classiques, dont les deux que nous allons étudier aujourd'hui : le tri par sélection et le tri par insertion. Ils sont simples à comprendre, parfaits pour débuter en algorithmique, et tu devras savoir les coder en Python.
Le tri par sélection : chercher le minimum
Imagine que tu doives ranger une pile de livres du plus petit au plus grand. Une méthode intuitive serait de :
1. Regarder toute la pile et prendre le plus petit livre.
2. Le placer en première position.
3. Recommencer avec le reste de la pile, en cherchant désormais le plus petit parmi les livres restants, et le placer à la suite.
C'est exactement le principe du tri par sélection (Selection Sort).
L'algorithme pas à pas
Prenons une liste en désordre : [64, 25, 12, 22, 11].
Première passe : On parcourt toute la liste pour trouver le minimum (11). On l'échange avec le premier élément (64). Liste : [11, 25, 12, 22, 64]. La première position est triée.
Deuxième passe : On cherche le minimum dans le sous-tableau non trié [25, 12, 22, 64]. C'est 12. On l'échange avec le premier élément de ce sous-tableau (25). Liste : [11, 12, 25, 22, 64]. Les deux premières positions sont triées.
On continue ainsi jusqu'à ce que toute la liste soit ordonnée.
Implémentation en Python
Voici comment coder cet algorithme de manière claire et pédagogique :
def tri_selection(liste): n = len(liste) # On parcourt tous les éléments sauf le dernier for i in range(n-1): # On suppose que l'élément minimum est à la position i indice_min = i # On cherche le vrai minimum dans la partie non triée for j in range(i+1, n): if liste[j] < liste[indice_min]: indice_min = j # On échange l'élément à la position i avec le minimum trouvé liste[i], liste[indice_min] = liste[indice_min], liste[i] return liste # Test ma_liste = [64, 25, 12, 22, 11] print("Liste triée :", tri_selection(ma_liste.copy())) # Affiche : [11, 12, 22, 25, 64]
Le tri par insertion : comme un jeu de cartes
Maintenant, imagine que tu tries tes cartes à jouer dans ta main. Tu prends les cartes une à une et tu les insères à la bonne place parmi celles déjà triées. C'est le principe du tri par insertion (Insertion Sort). C'est un algorithme dit "naturel", car c'est souvent comme cela que nous trions intuitivement.
L'algorithme pas à pas
Reprenons notre liste : [64, 25, 12, 22, 11].
On considère que le premier élément [64] est déjà un "sous-tableau trié".
Première insertion : On prend l'élément suivant (25). On le compare avec 64. 25 < 64, donc on décale 64 vers la droite et on insère 25 avant. Liste : [25, 64, 12, 22, 11].
Deuxième insertion : On prend 12. On le compare avec les éléments du sous-tableau trié [25, 64] de la droite vers la gauche pour trouver sa place. 12 < 64, on décale. 12 < 25, on décale. On insère 12 au début. Liste : [12, 25, 64, 22, 11].
On répète le processus jusqu'à la fin de la liste.
Implémentation en Python
Voici le code correspondant :
def tri_insertion(liste): n = len(liste) # On commence au 2ème élément (indice 1) for i in range(1, n): element_a_inserer = liste[i] j = i - 1 # On commence à comparer avec l'élément précédent # Tant qu'on n'est pas au début ET que l'élément à insérer est plus petit while j >= 0 and element_a_inserer < liste[j]: liste[j + 1] = liste[j] # On décale l'élément vers la droite j -= 1 # On a trouvé la bonne place, on insère liste[j + 1] = element_a_inserer return liste # Test ma_liste = [64, 25, 12, 22, 11] print("Liste triée :", tri_insertion(ma_liste.copy())) # Affiche : [11, 12, 22, 25, 64]
Comparaison et complexité : lequel choisir ?
Ces deux algorithmes ont des points communs : ils sont simples, ils trient "en place" (sans créer une nouvelle liste) et ils sont lents sur de grandes listes comparés à des algorithmes plus avancés comme le tri fusion ou rapide. Mais ils diffèrent sur des points clés.
Analyse de la complexité
- Tri par sélection : Sa complexité est toujours en O(n²), que la liste soit déjà triée ou non. En effet, il effectue systématiquement n(n-1)/2 comparaisons. Il fait peu d'échanges (au plus n).
- Tri par insertion : Sa complexité dans le pire des cas est aussi en O(n²) (liste triée à l'envers). Mais dans le meilleur cas (liste déjà triée), sa complexité est en O(n) ! C'est un algorithme adaptatif : il est très efficace sur des listes presque triées.
Quand les utiliser ?
- Le tri par sélection est utile pédagogiquement pour comprendre le concept de recherche de minimum/maximum et d'échange. Il est rarement utilisé en pratique pour de vraies données.
- Le tri par insertion est en revanche utilisé dans certains cas réels, notamment pour trier de petits ensembles de données ou des données partiellement triées. C'est aussi souvent la partie finale d'algorithmes plus complexes comme le tri rapide (quicksort).
Conclusion et pour aller plus loin
Tu maîtrises maintenant deux piliers des algorithmes de tri ! Le tri par sélection t'a appris à chercher un extremum et à structurer un algorithme en passes successives. Le tri par insertion t'a montré une méthode plus intuitive et adaptative, basée sur le décalage et l'insertion. En NSI, tu dois être capable de les expliquer, de les simuler sur papier et de les implémenter en Python. Pour t'entraîner, modifie le code pour trier dans l'ordre décroissant, ou compte le nombre de comparaisons et d'échanges effectués. Ces algorithmes sont ta porte d'entrée vers un monde fascinant : l'optimisation et l'analyse d'algorithmes !
