Tri par sélection

Le tri par sélection (ou tri par extraction) est un algorithme de tri par comparaison. Il est particulièrement simple, mais inefficace sur de grandes entrées, car il s'exécute en temps quadratique en le nombre d'éléments à trier.

Description

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
          si min ≠ i, alors échanger t[i] et t[j]

L'invariant de boucle suivant permet de prouver la correction de l'algorithme : à la fin de l'étape i, le tableau est une permutation du tableau initial et les i premiers éléments du tableau coïncident avec les i premiers éléments du tableau trié.

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.

Propriétés

Appliqué à un tableau, le tri par sélection est un tri sur place (les éléments sont triés dans la structure) mais n'est pas un tri stable (l'ordre d'apparition des éléments égaux n'est pas préservé).

Appliqué à une liste, le tri par sélection est stable à condition de déplacer la première occurence du plus petit élément à chaque étape.

Complexité

Dans tous les cas, pour trier n éléments, le tri par sélection effectue n(n-1)/2 comparaisons. Sa complexité est donc Θ(n²). De ce point de vue, il est inefficace puisque les meilleurs algorithmes s'exécutent en temps $O(n\,\log n)$. Il est même moins bon que le tri par insertion ou le tri à bulles, qui sont aussi quadratiques dans le pire cas mais peuvent être plus rapides sur certaines entrées particulières.

Par contre, le tri par sélection n'effectue que peu d'échanges :

• n-1 échanges dans le pire cas, qui est atteint par exemple lorsqu'on trie la séquence 2,3,…,n,1 ;
• $n-(1/2+\dots +1/n)\simeq n-\ln n$ en moyenne, c'est-à-dire si les éléments sont deux à deux distincts et que toutes leurs permutations sont équiprobables (en effet, l'espérance du nombre d'échanges à l'étape i est $(n-i)/(n-i+1)$) ;
• aucun si l'entrée est déjà triée.

Ce tri est donc intéressant lorsque les éléments sont aisément comparables, mais coûteux à déplacer dans la structure.

Implémentations

Une mise en œuvre simple du tri par sélection sur un tableau d'entiers en C :

typedef int tab_entiers[MAX];

void selection(tab_entiers t)
{
     int i, mini, j , x;
     for(i = 0 ; i < MAX - 1 ; i++)
     {
         mini = i;
         for(j = i+1 ; j < MAX ; j++)
              if(t[j] < t[mini])
                  mini = j;
         if(mini != i)
         {
             x = t[i];
             t[i] = t[mini];
             t[mini] = x;
         }
     }
}

Une mise en œuvre simple du tri par sélection sur un tableau d'entiers en Python :

import random

MAX_LENGTH = 100
un_tableau = [ k for k in range(0,MAX_LENGTH) ]
random.shuffle(un_tableau)

for k in range(0,MAX_LENGTH) :
    min = k
    for l in range(k+1, MAX_LENGTH) :
        if un_tableau[l] < un_tableau[min] :
            min = l
    if min is not k :
        number = un_tableau[k]
        un_tableau[k] = un_tableau[min]
        un_tableau[min] = number

Une mise en œuvre simple du tri par sélection sur un tableau d'entiers en PHP :

$count = count($arrayOf);
for($i=0;$i<$count-1;$i++)
 {
 	$min = $i;
	$minV = $arrayOf[$min];
 	for($j=$i+1;$j<$count;$j++)
 	{
 		if($arrayOf[$j] < $minV)
 		{
 			$min = $j;
			$minV = $arrayOf[$min];
 		}
 	}
 
 	if($min != $i)
 	{
 		$arrayOf[$min] = $arrayOf[$i];
 		$arrayOf[$i] = $minV;
 	}
 }

Le tri par sélection en Pascal (en ordre croissant)

 procedure TriSelection(n : integer ; var t : tab);
 var i, j, min, tmp : integer;
 begin
    for i := 1 to n - 1 do begin
       min := i;
 
       for j := i + 1 to n do
          if (t[j] < t[min]) then min:=j;
 
       if (i <> min) then begin
          tmp := t[i];
          t[i] := t[min];
          t[min] := tmp;
       end;
    end; 
 end;

Le tri par sélection en Java (en ordre croissant)

 public void sortBySelection(int[] t, int sizeOfTheCollection) {

     int i, min, j , x;
     for(i = 0 ; i < sizeOfTheCollection - 1 ; i++)
     {
         min = i;
         for(j = i+1 ; j < sizeOfTheCollection; j++)
              if(t[j] < t[min])
                  min = j;
         if(min != i)
         {
             x = t[i];
             t[i] = t[min];
             t[min] = x;
         }
     }

 }

Le tri par sélection en Caml (en ordre croissant):

let tri_select t =
  let n = vect_length t and m = ref(0) and i = ref(0) in
     for j=0 to (n - 2) do
       m := t.(j);
       i := j;
       for k = (j + 1) to (n - 1) do
          if !m < t.(k) then begin
                             m:= t.(k);
                             i:= k;
                             end
                             
       done;       
   t.(!i) <- t.(j); t.(j) <- !m;
  done;
t;;