Le tri par sélection - avec explication -

Le tri par sélection consiste à trouver dans le tableau l'indice de l'élément le plus petit, c.à.d. l'entier min tel que (T[k] >= T[min]) quel que soit k.

Une fois ce indice trouvé, les éléments T[1] et T[min] sont échangés (cet échange nécessite une variable temporaire de type entier) puis la même procédure est appliquée sur la suite d'éléments T[2], T[3], ..., T[N].

 

/* Procédure de tri par sélection */

procedure triSelection(entier[] T)

   entier i, k;

   entier min;

   entier temp;

   pour i allant de 1 à N-1 [1] faire

      /* recherche du numéro du minimum */

      min ß i;

      pour k allant de i+1 à N [1] faire

         si (T[k] < T[min]) alors

           min <- k;

         fin si

      fin pour

      /* échange des valeurs entre la case courante et le minimum */

      temp <- T[i];

      T[i] <- T[min];

      T[min] <- temp;

   fin pour

fin procedure

Il est aisé de compter le nombre d'opérations. Quel que soit l'ordre du tableau initial, le nombre de comparaisons reste le même, ainsi que le nombre d'échanges.

Le nombre total de comparaisons est donc de :

et le nombre d'échanges est (N-1).

En ce qui concerne sa complexité, on dit que le tri par sélection est en O (N²), à la fois dans le meilleur des cas, en moyenne et dans le pire des cas, c'est-à-dire que son temps d'exécution est de l'ordre du carré du nombre d'éléments à trier.