Tri par tas

Range la liste en tas, un arbre où chaque parent est plus grand que ses enfants. Puis il déplace la plus grande valeur à la fin, encore et encore.

meilleur cas Ω(n log n)
cas moyen Θ(n log n)
pire cas O(n log n)
espace O(1)
non stable
en place

Que veulent dire ces termes ?

Meilleur cas : comment le temps grandit avec la taille n de la liste quand l'entrée est la plus facile pour cet algorithme.
Cas moyen : le temps habituel selon n. En n², deux fois plus de valeurs prennent quatre fois plus de temps ; n log n croît bien moins vite.
Pire cas : la croissance sur l'entrée la plus difficile. Utile quand la vitesse ne doit jamais chuter.
Espace : la mémoire supplémentaire nécessaire en plus de la liste. 1 veut dire quelques variables, n une copie de la liste.
Stable : deux valeurs égales gardent leur ordre d'origine. Important quand on trie des fiches selon un seul champ.
En place : trie à l'intérieur de la liste elle-même, sans deuxième liste.

comparaison
déplacement
à sa place finale

0 / 299 étapes

Comparaisons Échanges

Lancez la lecture : les lignes montrent comment le coût grandit

Vitesse 8 étapes / s

Espace : lecture ou pause. Flèches gauche et droite : pas à pas. Origine et Fin : sauter.

Essayez : Choisissez une liste inversée. Construire le tas ne demande presque aucun échange, puis chaque tour déplace la plus grande valeur à la fin.

Comment ça marche

Le tas est rangé dans la liste elle-même : la valeur en position i a ses enfants en positions 2i+1 et 2i+2, et la plus grande valeur est toujours au début. On l'échange avec la dernière valeur, on réduit le tas d'une valeur et on le répare. La partie triée grandit depuis la droite.

Quand le choisir

Quand il faut une vitesse qui reste bonne même dans le pire cas, sans mémoire en plus, par exemple sur de petits appareils. En moyenne, il est plus lent que le tri rapide, et on s'en sert donc souvent comme filet de sécurité.