Tri par Sélection

L'auteur

Site personnel

Liens sociaux

Viadeo Twitter Facebook Share on Google+   

I. Introduction

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

II. Fonctionnement

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:

5 3 1 2 4

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 :

5 3 1 2 4

on fait l'échange :

1 3 5 2 4

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

1 3 5 2 4

on fait l'échange :

1 2 5 3 4

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

1 2 5 3 4

on fait l'échange :

1 2 3 5 4

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

1 2 3 5 4

on fait l'échange :

1 2 3 4 5

Et voilà, on obtient le tableau trié :

1 2 3 4 5

III. 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)
 
Sélectionnez

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
 
Sélectionnez

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

 
Sélectionnez

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

IV. 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...

Image non disponible

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

Liste de mes articles :
Delphi 6 : Réalisation d'un explorateur de fichiers
Delphi 6 : Création d'un menu 'à la Office 2000'
Delphi 7: Réaliser un Client FTP à l'aide des composants Indy
Delphi 7 : Donner le style Windows XP à vos applications sous Windows XP
Portage d'applications CLX entre Delphi 6 et Kylix
Tri par Sélection
Ce document est issu de http://www.developpez.com et reste la propriété exclusive de son auteur. La copie, modification et/ou distribution par quelque moyen que ce soit est soumise à l'obtention préalable de l'autorisation de l'auteur.