Les TRIS en algorithmique : 2ème partie (Tri par extraction)

By: XTT on 11:02:00

Principe du tri par extraction :

Cette méthode utilise en plus du tableau à trier un deuxième tableau dans lequel on place les éléments triès.

On cherche le plus petit élément dans le premier tableau et on le place au début du deuxième tableau.

 

Ensuite on cherche le plus petit élément parmi ceux non encore sélectionnées du premier tableau et on le place dans le deuxième tableau jusqu’à ce que tous les éléments soient recopiés dans le deuxième tableau. A chaque fois qu’un élément est sélectionné, il est remplacé par une valeur spéciale pour ne pas être présélectionné une deuxième fois.

Algorithme du tri par extraction :

Var

T,T1 : tableau [1..100] de réels ;

n,ind,i,j : entiers ;

max : reel;

Début

            Pour i <-- 1 à n faire

                     Ind <-- 1 ;

                     Pour  j <-- 2 à n faire

                            Si T[ind] > T[j] alors

                                   ind <-- j ;

                           FinSi

                     FinPour j

                    T1[i] <-- T[ind] ;

                    T[ind] <-- max ;

        FinPour i

Fin

On note max la valeur spéciale, plus grande que tous les éléments du tableau (dans le cas d’un tri croissant) et plus petite que tous les éléments du tableau (dans le cas d’un tri décroissant). Avant de lancer l’algorithme de tri par extraction, on peut appliquer au tableau T un algorithme de recherche du maximum auquel on ajoute 1 pour déterminer la valeur de max (max=max(T) + 1), ind est l’indice du plus petit élément trouvé.

Exemple d’utilisation :

Soit le tableau suivant composé de 6 éléments (n=6) .

15

2

24

-8

0

4

max = maximum(T) + 1 = 24 + 1 = 25.

i=1 :

15

2

24

25

0

4

I=2 :

15

2

24

25

25

4

i=3

15

25

24

25

25

4

i=4

15

25

24

25

25

25

i=5

25

25

24

25

25

25

i=6

25

25

25

25

25

25

Le résultat dans le tableau T1 :

-8

0

2

4

15

24

Remarquons qu’à la fin, le tableau T ne contient plus que les valeurs spéciales 25. Et T1 contient les anciens éléments de T triés par ordre croissant.

Conclusion :

Le tri par extraction est un algorithme de tri par comparaison. Il est particulièrement simple, mais inefficace sur de grandes entrées, car il s'exécute en temps quadratique en le nombre d'éléments à trier.