Tri par Sélection
Date de publication :
26 Avril 2002
Date de mise a jour :
26 Avril 2002
Par
darkskull (Dark Skull Software)
I. Introduction
II. Fonctionnement
III. Détails
IV. Conclusion
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...
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 :
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 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)
type
TIntegerArray = array of Integer;
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
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;
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.
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 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...
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.
|
