Nicolas DAILLY
www.dailly.info > Dossiers techniques > Algorithmes de Tri > Tri par sélection

Tri par sélection

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.

531264
531246
431256
231456
213456
123456
Pseudo langage
C / C++ Caml Java OCaml

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.

Complexité de l'algorithme du tri bulle


- Accueil des algorithmes de tri
- Article précédent : le tri par création
- Article suivant : le tri par insertion


© 2000-2017 ~ Nicolas Dailly
Page générée le 25/05/2017 à 22:19:47 ~ Site réalisé avec SPIP