Tri par sélection

Le tri par sélection

Le principe du tri par sélection/échange (ou tri par extraction) est d'aller chercher le plus petit élément du vecteur pour le mettre en premier, puis de repartir du second élément et d'aller chercher le plus petit élément du vecteur pour le mettre en second, etc...

L'animation ci-après détaille le fonctionnement du tri par sélection :

Démonstration du tri par sélection

  1. PROCEDURE tri_Selection ( Tableau a[1:n])
  2.     POUR i VARIANT DE 1 A n - 1 FAIRE
  3.         TROUVER [j] LE PLUS PETIT ELEMENT DE [i + 1:n];
  4.         ECHANGER [j] ET [i];
  5. FIN PROCEDURE;
  1. let rec plus_petit tab debut fin =
  2.     if (debut == fin) then debut else
  3.     let temp =plus_petit tab (debut+1) fin in
  4.     if tab.(debut) > tab.(temp) then temp else debut;;
  5.        
  6. let tri_selection tableau =
  7.     for en_cours = 0 to 18 do    
  8.         let p = plus_petit tableau (en_cours+1) 19 in
  9.         begin
  10.             if p <> en_cours then
  11.             begin
  12.                 let a = tableau.(en_cours) in
  13.                 begin
  14.                     tableau.(en_cours) <- tableau.(p);
  15.                     tableau.(p) <- a;
  16.                 end;
  17.             end;
  18.         end;
  19.     done;
  20. tableau;;
  1. type tab = array[1..20] of integer;
  2. procedure tri_selection(var tableau : tab);
  3. var
  4.   temp: integer;
  5.   en_cours, plus_petit, j : integer;
  6.  
  7. begin
  8.   for en_cours:= 1 to 19 do
  9.   begin
  10.     plus_petit := en_cours;
  11.     for j:= en_cours + 1 to 20 do
  12.     begin
  13.       {Recherche de l'element le plus petit}
  14.       if tableau[j] < tableau[plus_petit] then plus_petit:= j;
  15.     end;
  16.     {On place le plus petit à la position en_cours}
  17.     temp:= tableau[en_cours];
  18.     tableau[en_cours]:= tableau[plus_petit];
  19.     tableau[plus_petit]:=temp;
  20.   end;
  21. end;
  1. def tri_selection(tableau):
  2.     nb = len(tableau)
  3.     for en_cours in range(0,nb):    
  4.         plus_petit = en_cours
  5.         for j in range(en_cours+1,nb) :
  6.             if tableau[j] < tableau[plus_petit] :
  7.                 plus_petit = j
  8.         if min is not en_cours :
  9.             temp = tableau[en_cours]
  10.             tableau[en_cours] = tableau[plus_petit]
  11.             tableau[plus_petit] = temp
  1. void tri_selection(int *tableau, int taille)
  2. {
  3.      int en_cours, plus_petit, j, temp;
  4.  
  5.      for (en_cours = 0; en_cours < taille - 1; en_cours++)
  6.      {
  7.          plus_petit = en_cours;
  8.          for (j = en_cours 1; j < taille; j++)
  9.               if (tableau[j] < tableau[plus_petit])
  10.                   plus_petit = j;
  11.           temp = tableau[en_cours];
  12.           tableau[en_cours] = tableau[plus_petit];
  13.           tableau[plus_petit] = temp;
  14.      }
  15. }

Cet algorithme n'est pas stable, comme vous pouvez le vérifier ici.

Si on applique cet algorithme au petit jeu de la page précédente, on obtient :



 


Complexité du tri par selection

Dans tous les cas l'algorithme effectuera n(n-1)/2 comparaisons. Sa complexité est donc en Θ(n2).

Complexite du tri par selection Nombre d'opérations Nombre d'elements à trier Θ(n2)