Tris par comparaison
Algorithmes lents
Ces algorithmes sont lents pour plus de 20 éléments parce qu'ils sont en O(n2).
Tri à bulles : Algorithme quadratique, T(n) = O(n2), en moyenne et dans le pire des cas, stable et en place ; amusant mais pas efficace
Tri par sélection : Algorithme quadratique, T(n) = O(n2), en moyenne et dans le pire des cas, pas stable si tri sur place ; rapide lorsque l'on a moins de 7 éléments
Tri par insertion : Algorithme quadratique, T(n) = O(n2), en moyenne et dans le pire des cas, stable et en place. C'est le plus rapide et le plus utilisé pour des listes de moins de 15 éléments ;
Algorithmes plus rapides
Tri de Shell (shell sort) : Amélioration du tri par insertion, mais pas stable. Complexité : au pire O(n \log^2 n) pour la série de pas 2^p3^q et O(n\sqrt{n}) pour la série de pas 2^k-1. On ne connaît pas de série donnant O(n \log n).
Tri fusion (merge sort) : O(n \log n) en moyenne et dans le pire des cas, stable mais pas en place3 ;
Tri rapide (quick sort) : O(n \log n) en moyenne, mais en O(n^2) (quadratique) au pire cas4, en place mais pas stable
Introsort : Amélioration du tri rapide, qui permet une exécution en O(n \log n) dans tous les cas.
Tri par tas (heap sort) : O(n \log n) en moyenne et dans le pire des cas, en place mais pas stable. Toujours environ deux fois plus lent que le tri rapide, c'est-à-dire aux alentours de O(n \log n), il est donc intéressant de l'utiliser si l'on soupçonne que les données à trier seront souvent des cas quadratiques pour le tri rapide ;
Tri par ABR : O(n \log n) en moyenne, O(n^2) dans le pire des cas. Ce tri est un des plus lents (parmi les tris rapides) et des plus gourmands en mémoire à cause de la structure d'arbre binaire à manipuler. Il est possible de le rendre O(n \log n) dans tous les cas en maintenant un arbre équilibré (Arbre AVL).
Smoothsort : tri inspiré du tri par tas en utilisant un arbre non inversé, ce tri est très rapide pour les ensembles déjà presque triés, sinon, il est en O(n \log n). Tri en place mais pas stable
Partager