1NSI : Algorithmes de Tri⚓︎
Problématique⚓︎
On suppose qu'on a une liste de nombres (ou d'éléments qu'il est possible d'ordonner, par exemple des chaînes de caractères) et on cherche comment on peut les trier dans l'ordre croissant. Dans ce chapitre on prendra pour exemple des cartes numérotées.
Les deux algorithmes au programme de première consistent à construire une nouvelle liste à partir de l'ancienne, tout en vidant l'ancienne liste, et en s'assurant que pendant toute la construction, la nouvelle liste est (et reste) triée.
Pourquoi étudier des algorithmes de tri ?⚓︎
Autant ne pas le cacher, ces algorithmes sont déjà implémentés (quel que soit le langage) dans des fonctions très performantes.
En Python, on utilise la fonction sort()
:
>>> tab = [4, 8, 1, 2, 6]
>>> tab.sort()
>>> tab
[1, 2, 4, 6, 8]
Le meilleur de nos futurs algorithmes de tri sera moins efficace que celui de cette fonction sort()
...
Malgré cela, il est essentiel de se confronter à l'élaboration manuelle d'un algorithme de tri :
- Le tri par insertion est le premier des deux algorithmes de tri que nous allons étudier
- puis nous étudierons le tri par sélection
Ces deux algorithmes ont pour particularité de :
- ne pas nécessiter la création d'une nouvelle liste : on dit qu'ils modifient la liste à trier
sur place . - ne pas faire intervenir de fonctions complexes (comme la recherche d'un minimum par exemple)