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.
- Ω(n log n)
- Θ(n log n)
- O(n log n)
- O(1)
- non
- oui
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
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é.