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

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.