Tri par sélection
Cherche la plus petite valeur restante et l'échange pour la mettre à la place suivante. Il fait très peu d'échanges, mais toujours le même nombre de comparaisons.
- Ω(n²)
- Θ(n²)
- O(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
- minimum actuel
- à sa place finale
Essayez : Choisissez une liste inversée. Le nombre de comparaisons reste exactement le même qu'avec n'importe quelle autre liste.
Comment ça marche
On parcourt la partie non triée pour trouver la plus petite valeur. On l'échange avec la première valeur non triée, et une valeur de plus est alors à sa place finale. Il examine toujours toutes les valeurs restantes, même si la liste est déjà triée.
Quand le choisir
Utile quand déplacer des données coûte cher mais que les lire coûte peu, car il fait au plus un échange par position. Dans presque tous les autres cas, le tri par insertion est un meilleur choix simple.