Les TRIS en algorithmique : 1ère partie

By: XTT on 10:25:00

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.