Tri par tas

Carte Peu commune · n° 180733

En informatique, le tri par tas (en anglais heapsort) est un algorithme de tri par comparaisons. Cet algorithme est de complexité asymptotiquement optimale. Sa complexité est proportionnelle à nlog⁡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 (plus précisément il ne nécessite qu'une allocation d'une zone mémoire de taille O(1)). Par contre, il n'est pas stable, c'est-à-dire que l'ordre original d'éléments auxquels est associée une même clé de tri n'est pas en général préservé. Son inconvénient majeur est sa lenteur comparé au tri rapide (qui est en moyenne deux fois plus 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[réf. nécessaire].

Lire sur Wikipédia · Image de:User:RolandH, CC BY-SA 3.0