Tri par Sélection



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


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 oeuvre. Dans cet article, je détaillerais 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...

Fonctionnement

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

  • 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.
  • Placer dans l'élément d'indice 2 de T la plus petite valeur présente dans la tranche de tableau T[2..N]
  • Placer dans l'élément d'indice 3 de T la plus petite valeur présente dans la tranche de tableau T[3..N]
  • 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'intevalle T[1..5] et de faire l'échange avec la valeur de la case d'indice 1 :



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



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




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



    Et voilà, on obtient le tableau trié:




    Détails

    Pour mettre en place le tri par sélection, il nous faut donc 4 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ère, 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)

    Fonction de recherche de l'indice du plus petit élément

    
    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 2 éléments du tableau


    fonction d'échange entre 2 éléments du tableau

    // Echange 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.


    procédure de tri

    // 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;
    




    Conclusion


    Le tri par insertion est un algorithme simple à mettre en oeuvre, 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...


    3 requête(s) SQL executée(s) en 0.001 Secs - Temps total de génération de la page : 0.007 Secs