Présentation
Le tri par sélection est l'un des tris les plus instinctifs. Le principe est que pour classer n valeurs, il faut rechercher la plus grande valeur et la placer en fin de liste, puis la plus grande valeur dans les valeurs restante et la placer en avant dernière position et ainsi de suite...
Considérons un tableau à n éléments. Pour effectuer le tri par sélection, il faut rechercher dans ce tableau la position du plus grand élément. Le plus grand élément est alors échangé avec le dernier élément du tableau. Ensuite, on réitère l'algorithme sur le tableau constitué par les (n-p) premiers éléments où p est le nombre de fois où l'algorithme a été itéré. L'algorithme se termine quand p=(n-1), c'est à dire quand il n'y a plus qu'une valeur à sélectionner ; celle ci est alors la plus petite valeur du tableau.
Exemple
Grandes étapes de l'évolution du tableau au fil de l'algorithme. En bleu, les valeurs déja traitées.
| 5 | 3 | 1 | 2 | 6 | 4 |
| 5 | 3 | 1 | 2 | 4 | 6 |
| 4 | 3 | 1 | 2 | 5 | 6 |
| 2 | 3 | 1 | 4 | 5 | 6 |
| 2 | 1 | 3 | 4 | 5 | 6 |
| 1 | 2 | 3 | 4 | 5 | 6 |
Complexité
La relative simplicité de cet algorithme fait qu'on lui attribut le qualificatif d' "algorithme naïf". Cela signifie que même si l'algorithme est correct, il est trop simple pour être réellement efficace. En effet, la complexité, en nombre de comparaisons, est analogue à la complexité du tri bulle optimisé. A la première itération, sont effectuées (n-1) comparaisons. A la pième itération, sont effectuées (n-p) comparaisons. Soit une complexité en O(n2) dont le calcul exact est donné par la formule suivante.
