Tri par Sélection

darkskull

- Titre : Tri par Sélection

- Auteur : darkskull

- Parution : 26 avril 2002

- Mise à jour : 8 décembre 2019

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

Sommaire

- I. Introduction

- II. Fonctionnement

- III. Détails

- IV. Conclusion

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 œ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…

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'intervalle 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 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;

IV - Conclusion

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)