Les TRIS en algorithmique : 1�re partie

Trier veut dire ordonner un ensemble d��l�ments, les ranger en ordre croissant ou d�croissant :

�        Tri croissant : si l��l�ment d�indice i est inf�rieur ou �gal � l��l�ment d�indice i+1.

�        Tri d�croissant : si l��l�ment d�indice i est sup�rieur ou �gal � l��l�ment d�indice i+1.

Le but du tri est de faciliter l�utilisation d�un ensemble de donn�es, par exemple pour un algorithme de recherche, fusion, �clatement . . .

Tri Interne � Tri Externe :

Un tri interne s�effectue sur des donn�es pr�sentes en m�moire centrale. L�acc�s aux informations ne prend que peu de temps. Pour �valuer le temps de calcul, on ne consid�re que le nombre de combinaisons et de permutations.

Un tri externe s�effectue sur des donn�es r�sidant en m�moires secondaires (disquettes, disques durs�). Dans ce cas le temps d�acc�s aux informations devient plus important car il s�agit d�un organe m�canique qui tourne. C�est pourquoi en g�n�ral, on cherche � minimiser le nombre d�acc�s aux m�moires secondaires.

Tr�s souvent, tri interne est �quivalent � tri de tableaux, et tri externe est �quivalent � tri de fichiers rang�s s�quentiellement.

 Quelques m�thodes de tri :

Il existe plusieurs m�thodes de tris. Nous allons pr�senter quelques-unes.

Dans tous les algorithmes qui suivront, on consid�re un tableau de 100 cases, dont n remplies par des valeurs r�elles. Nous nous int�resserons au tri croissant. La saisie et l�affichage des �l�ments sont suppos�es faites par d�autres algorithmes appelants.

Tri par SELECTION :

C�est l�une des m�thodes les plus simples pour trier les �l�ments d�un tableau : T [1], T [2], T [3]�, T [n]  en ordre croissant par exemple.

Nous allons balayer tous les �l�ments pour chercher le plus petit que nous �changeons avec T [1].

Nous r�p�tons en cherchant le plus petit �l�ment parmi T [2] jusqu�� T[n] que nous �changeons avec T [2] et ainsi de suite.

Apr�s (n-1) application de cette recherche et �change, les �l�ments du tableau sont tri�s.

Algorithme de s�lection :

Var

T : tableau : [1..100] de r�els ;

n,s,min,i,j : entiers ;

D�but

(* Tri des �l�ments du tableau *)

Pour i <-- 1 � (n-1) faire

    Min <-- T[i] ;

    Pour j <-- i+1 � n faire

         Si min > T[j] alors

             Min <-- T[j] ;

             s <-- j ;

         FinSi

   FinPour j

   Si min < T[i] alors

    T[s] <-- T[i] ;

    T[i] <-- min ;

   FinSi

FinPour i

Fin

On note min la valeur de minimum et s l�indice de cette valeur.

N.B : La pr�sentation des autres algorithmes se fera dans les prochains articles.