Tri par tas

Tri par tas

Une exécution de l'algorithme du tri par tas (Heapsort) trie une partie des valeurs permutées au hasard. Dans un premier temps, les éléments sont réarrangés pour respecter les conditions de tas. Avant le tri à proprement parler, la structure de l'arbre en tas est montrée brièvement par l'illustration.

Découvreur ou inventeur	J. W. J. Williams (en)
Date de découverte	1964
Problème lié	Algorithme de tri
Structure des données	Tableau
À l'origine de	Smoothsort

Complexité en temps

Pire cas	${\displaystyle O(n\log(n))}$
Moyenne	${\displaystyle O(n\log(n))}$
Meilleur cas	${\displaystyle O(n\log(n))}$

Complexité en espace

Pire cas	${\displaystyle O(1)}$

modifier - modifier le code - modifier Wikidata

En informatique, le tri par tas (en anglais heapsort) est un algorithme de tri par comparaisons. Cet algorithme est de complexité asymptotiquement optimale^[1]. Sa complexité est proportionnelle à ${\displaystyle n\log n}$ où ${\displaystyle 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 ${\displaystyle O(1)}$)^[2]. 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]}.