- Définition : Ce sont des algorithmes qui partant d’une liste en renvoie une version ordonnée
Exemples : [5,1,4,3,2] → [1,2,3,4,5] ou [8,4,6,2,3,8,6] -> [2,3,4,6,6,8,8] - Variété : Il existe de nombreux algorithmes de tri qui ont été développés . On peut citer, parmi les plus courants : par insertion, par sélection, à bulle, rapide (quicksort), fusion, par tas, par comparaison, Smoothsort, Timsort,….
- Pourquoi trier ? Et bien, remarquons qu’on peut trier à peu près n’importe quoi. Le tout est de définir une comparaison :
fichiers par taille, livres par ordre alphabétique, dossier par profondeur dans une arborescence, joueurs par score, fichiers par date d’édition etc. - Mais pourquoi aurait-on besoin de PLUSIEURS algorithmes ?
Tout dépend des données à trier, si elles sont très nombreuses on va choisir un algorithme qui va limiter
la complexité calculatoire (temporelle)
ou si elles occupent beaucoup d’espace, on choisit un algorithme qui va limiter la complexité spatiale - Doit-on programmer nous même pour trier ? Tout dépend des langages !
Python (mais beaucoup d’autres aussi) dispose de son propre tri qui est le plus efficace. Python emploie Timsort (Tim Peters, 2002) qui résout à la fois presque tous les problèmes.
Mais nous n'utiliserons pas les algorithmes de Python et nous allons étudier les deux algorithmes du programme de 1ère NSI