Tri par Sélection

Il existe de nombreux algorithmes de tri. Je vais vous expliquer ici le fonctionnement du tri par sélection, qui a l'avantage d'être un des plus simples à mettre en œuvre. Dans cet article, je détaillerai le tri sur un tableau d'entiers, mais cet algorithme est tout aussi valide pour trier un tableau de chaînes de caractères, de flottants, ou de tout autre type tant qu'on peut émettre une comparaison…

Considérons un tableau T de N chaînes de caractères (indicées de 1 à N).
Le principe est le suivant :

1. Placer dans l'élément d'indice 1 du tableau T la plus petite valeur présente dans le tableau ; pour cela, on recherche la plus petite valeur dans T et on la place dans T[1] ; la valeur qui se trouvait auparavant dans T[1] est mise à sa place ;
2. Placer dans l'élément d'indice 2 de T la plus petite valeur présente dans la tranche de tableau T[2..N] ;
3. Placer dans l'élément d'indice 3 de T la plus petite valeur présente dans la tranche de tableau T[3..N] ;
4. et ainsi de suite jusqu'à l'étape N-1.

Par exemple, avec le tableau d'entiers suivants :

La première étape consiste à identifier la plus petite valeur de l'intervalle T[1..5] et de faire l'échange avec la valeur de la case d'indice 1 :

on fait l'échange :

La 2° étape consiste à mettre la plus petite valeur de l'intervalle T[2..5] dans la case 2 :

on fait l'échange :

La 3° étape consiste à mettre la plus petite valeur de l'intervalle T[3..5] dans la case 3 :

on fait l'échange :

La 4° et dernière étape consiste à mettre la plus petite valeur de l'intervalle T[4..5] dans la case 4 :

on fait l'échange :

Et voilà, on obtient le tableau trié :

Pour mettre en place le tri par sélection, il nous faut donc quatre opérateurs/fonctions/procédure :

• un opérateur de comparaison
  - il suffit d'utiliser l'opérateur de comparaison « < ». Pour les chaînes de caractères, l'opérateur « < » fonctionne aussi, et la comparaison se fait selon l'ordre alphabétique ;
• une fonction de recherche de l'indice du plus petit élément
  Dans une liste à partir d'un indice donné (par exemple, sur une liste de 50 éléments, une fonction qui puisse chercher le plus petit élément à partir de l'indice 10 jusqu'à l'indice 50)

type
  TIntegerArray = array of Integer;

// Recherche du plus petit élément de T dans l'intervalle StartIndex..Longueur(T)
function SmallestIndex(const T: TIntegerArray; const StartIndex: integer): integer;
var
  i: Integer;
  tmp: Integer;
begin
  Result := StartIndex;
  tmp := T[StartIndex];
  for i := StartIndex to Pred(Length(T)) do
    begin
      if tmp > T[i] then
        begin
          Result := i;
          tmp := T[i];
        end;
    end;
end;

• une fonction d'échange entre deux éléments du tableau

// Échange de 2 éléments de T
procedure SwapElts(var T: TIntegerArray; const index1, index2: integer);
var
  tmp: integer;
begin
  if index1 <> index2 then
    begin
      tmp := T[index1];
      T[index1] := T[index2];
      T[index2] := tmp;
    end;
end;

• la procédure de tri

Une procédure qui, pour chaque élément du tableau jusqu'à l'avant-dernier, recherche le plus petit élément entre l'indice courant et la fin du tableau, et fait l'échange si ce n'est pas lui-même.

// Le tri en lui-même
procedure Sort(var T: TIntegerArray);
var
  i: integer;
begin
  if (Length(T) > 0 ) then
    begin
      for i := 0 to Pred(Length(T)) do
        begin
          SwapElts(T, i, SmallestIndex(T, i));
        end;
    end;
end;

Le tri par insertion est un algorithme simple à mettre en œuvre, qui est assez rapide pour des petits tableaux, mais qui peut devenir assez lent pour de très grands tableaux . Il existe d'autres algorithmes comme le tri à bulle qui est similaire à cet algorithme, le tri fusion et le tri rapide, dont certains donnent de meilleures performances sur de grands tableaux…

Télécharger le projet exemple (2 ko)