Tri par sélection

Le tri par sélection (ou tri par extraction) est un algorithme de tri par comparaison. Cet algorithme est simple, mais considéré comme inefficace, car il s'exécute en temps quadratique en le nombre d'éléments à trier, et non en temps pseudo linéaire.

Description, pseudo-code et variantes

Animation représentant le tri par sélection

Sur un tableau de n éléments (numérotés de 1 à n), le principe du tri par sélection est le suivant :

  • rechercher le plus petit élément du tableau, et l'échanger avec l'élément d'indice 1 ;
  • rechercher le second plus petit élément du tableau, et l'échanger avec l'élément d'indice 2 ;
  • continuer de cette façon jusqu'à ce que le tableau soit entièrement trié.

En pseudo-code, l'algorithme s'écrit ainsi :

  procédure tri_selection(tableau t, entier n)
      pour i de 1 à n - 1
          min ← i
          pour j de i + 1 à n
              si t[j] < t[min], alors min ← j
          fin pour
          si min ≠ i, alors échanger t[i] et t[min]
      fin pour
  fin procédure

Une variante consiste à procéder de façon symétrique, en plaçant d'abord le plus grand élément à la fin, puis le second plus grand élément en avant-dernière position, etc.

Le tri par sélection peut aussi être utilisé sur des listes. Le principe est identique, mais au lieu de déplacer les éléments par échanges, on réalise des suppressions et insertions dans la liste.

Other Languages