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.

meilleur cas Ω(n²)
cas moyen Θ(n²)
pire cas O(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
minimum actuel
à sa place finale

0 / 399 é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. 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.