Sort.
Analyse
Un algorithme de tri peut être plus ou moins performant en terme de :
- rapidité (complexité temporelle) : au mieux en
O(n log(n))
- consommation mémoire (complexité spatiale)
suivant l'algorithme utilisé et son adéquation à l'ensemble à trier,
notamment :
- sa taille : certains algorithmes réputés "mauvais" sont plus
efficaces sur des petits ensembles par exemple, tandis que d'autres capables de tris externes
(tris d'ensemble de données
énormes car capable de fonctionner sur des sous-ensembles, l'ensemble total ne tenant pas
en mémoire).
- son état avant tri :
- plus ou moins déjà trié (pratiquement trié, trié à l'envers, ou réellement aléatoire).
- sa distribution (éléments égaux répétés par exemple)
Il n'y a donc pas d'algorithme idéal, et les meilleures solutions de tri sont adaptatives
(capables de mobiliser/combiner plusieurs algorithmes en fonction de ces critères).
Un algorithme de tri peut aussi est stable ou non, à savoir que les
éléments égaux ne sont pas réordonnés (leurs positions relatives sont garanties inchangées après le tri).
Exemples
Notes
- Les listes chaînées ne sont pas réputées adaptées à un tri efficace,
parce qu'elles ne permettent pas d'accès aléatoire (en O(1)) à n'importe quel élément (il faut à chaque fois
parcourir la liste en O(n) pour trouver un élément). Elles sont toutefois généralement triées par fusion.