Tri par insertion
Construit une partie triée à gauche, une valeur à la fois. Chaque nouvelle valeur est sortie, puis glisse vers la gauche jusqu'à tomber sur une valeur plus petite.
- Ω(n)
- Θ(n²)
- O(n²)
- O(1)
- oui
- 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
- en main
- partie triée
- à sa place finale
Paires dans le désordre : 154 (au départ : 154) dans le désordre remise en ordre Les deux axes : valeurs de la plus petite à la plus grande
Lancez la lecture : les lignes montrent comment le coût grandit
Appuyez sur lecture ou avancez pas à pas.
Espace : lecture ou pause. Flèches gauche et droite : pas à pas. Origine et Fin : sauter.
Essayez : Choisissez une liste presque triée. Presque rien ne se décale, donc le tri se termine en très peu d'étapes.
Comment ça marche
La partie gauche est toujours triée. On sort la valeur suivante, on décale d'une position vers la droite chaque valeur plus grande de la partie triée, puis on pose la valeur dans le trou. Beaucoup de gens trient ainsi les cartes qu'ils ont en main.
Quand le choisir
Un bon choix pour les petites listes et pour les listes presque triées, où il est très rapide. Les vraies bibliothèques de tri s'en servent pour les petits morceaux de liste, à l'intérieur de méthodes plus rapides.