Présentation :
Tri par Tas :
Le tri par tas est un algorithme de tri par comparaison. Cet algorithme est de complexité asymptotiquement optimale, c’est-à-dire que l’on démontre qu’aucun algorithme de tri par comparaison ne peut avoir de complexité asymptotiquement meilleure. Sa complexité est proportionnelle à N log N où N est la longueur du tableau à trier. Le tri par tas se fait en place, c’est-à-dire qu’il ne nécessite pas l’allocation d’une zone mémoire supplémentaire.
Son inconvénient majeur est sa lenteur comparée au tri rapide : sur un tableau de taille importante, il sera amené à traiter un nombre élevé d’emplacements mémoire dont l’éloignement peut dépasser la capacité du cache, ce qui ralentit l’accès à la mémoire et l’exécution de l’algorithme.
Tri par insertion :
Le tri par insertion est un algorithme de tri classique, que la plupart des personnes utilisent naturellement pour trier des cartes : prendre les cartes mélangées une à une sur la table, et former une main en insérant chaque carte à sa place.
En général, le tri par insertion est beaucoup plus lent que d’autres algorithmes comme le tri rapide et le tri fusion pour traiter de grandes séquences, car sa complexité asymptotique est quadratique.
Le tri par insertion est cependant considéré comme le tri le plus efficace sur des entrées de petite taille. Il est aussi très rapide lorsque les données sont déjà presque triées. Pour ces raisons, il est utilisé en pratique en combinaison avec d’autres méthodes comme le tri rapide.
Sources : trie
Merci à wikipedia pour les définitions.