Tri par sélection

Un article de Wikipédia, l'encyclopédie libre.

Le tri par sélection (ou tri par extraction) est un des algorithmes de tri les plus triviaux. Il consiste en la recherche soit du plus grand élément (ou le plus petit) que l'on va replacer à sa position finale c'est-à-dire en dernière position (ou en première), puis on recherche le second plus grand élément (ou le second plus petit) que l'on va replacer également à sa position finale c'est-à-dire en avant-dernière position (ou en seconde), etc., jusqu'à ce que le tableau soit entièrement trié.

Le tri par sélection est intéressant lorsque les éléments sont aisément comparables mais coûteux à déplacer dans la structure. Ainsi, le nombre de comparaisons sera toujours supérieur ou égal à ce qui est nécessaire pour effectuer un tri par insertion ou un tri à bulles. Par contre, s'il n'est pas possible de faire des insertions dans la structure en temps constant (O(1)), le nombre d'échanges sera en moyenne très inférieur.

[modifier] Propriétés

Le nombre de comparaisons nécessaires pour un tri est de N(N+1)/2 (où N est la quantité de donnée à trier).
Le nombre d'échanges, lui, est de l'ordre de N.

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é).

[modifier] Complexité

Meilleur cas : O(n²), le tableau est déjà trié, on doit parcourir tout le tableau mais on peut économiser l'échange
Pire cas : O(n²), le tableau est trié en ordre inverse
Moyenne : O(n²)

[modifier] Implémentations

Algorithme : (« ⇐ » note l'affectation, et « ⇌ » note l'échange de valeur)

tab_entiers[MAX]
 
PROCEDURE selection (tab_entiers t) 
        POUR CHAQUE i entier  dans  [0 ;  MAX - 1 [
                min ⇐ i
                POUR CHAQUE j entier dans [ i+1 ; MAX [
                        SI t[j] < t[min] ALORS
                                min ⇐ j
                SI min ≠ i ALORS
                        t[i] ⇌ t[min]

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, min, j , x;
    for(i = 0 ; i < MAX - 1 ; i++)
    {
        min = i;
        for(j = i+1 ; j < MAX ; j++)
             if(t[j] < t[min])
                 min = j;
        if(min != i)
        {
            x = t[i];
            t[i] = t[min];
            t[min] = x;
        }
    }
}

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

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

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;