Algorithmes de tri

Algorithmes de TRI Algorithmique & Programmation

Enseignant: Mr SAYARI Page 1 /4 4 S.INFO

I. Rappels 1) Activité 1 (Tri à bulles)

a) Principe Le principe de cette méthode de tri consiste à balayer tout le tableau, comparer les éléments consécutifs

et les échanger s'ils ne sont pas dans le bon ordre.

Cette méthode peut se traduire par l’algorithme formel suivant :

Comparer la première paire des éléments,

1- Si T [ 1 ] > T [ 2 ]alors permuter T [ 1 ] et T [ 2 ] et tenir compte de cette action.

2- Aller à la paire suivante et répéter les étapes 1 et 2 jusqu’à comparer la dernière paire.

3- Si une permutation a été réalisée (ou plusieurs) alors répéter ce qu’on vient de faire, sinon le tableau

est trié.

b) Algorithme

0) DEF PROC Tri_bulles( var T :tab ; N : entier)

1) Répéter echange Faux Pour i de 1 à N - 1 Faire Si T [ i ] > T [ i + 1 ] Alors aux T [ i ] T [ i ] T [ i + 1 ] T [ i + 1 ] Aux echange vrai Fin Si Fin Pour

Jusqu’à (echange = Faux) 2) Fin Tri_bulles

2) Activité 2 (Tri par séléction) a) Principe Cette méthode peut se traduire par l’algorithme formel suivant :

1- Comparer tous les nombres afin de sélectionner le plus petit (ordre croissant), 2- Échanger le plus petit élément trouvé avec le premier élément, 3- Refaire les étapes 1 et 2 et rechercher le plus petit du tableau sauf le premier puis l’échanger avec le

second.

b) Algorithme

0) DEF PROC Tri_sélection( var T :tab ; N : entier) 1) Pour i de 1 à N - 1 Faire posmin i Pour j de i+1 à N Faire Si T [ j ] < T [ posmin ] Alors posmin j Fin Si Fin Pour Si i < > posmin Alors aux T [ i ] T [ i ] T [posmin ] T [posmin ] aux Fin Si Fin Pour

2) Fin Tri_selection

PROC Permut (T [ i ], T [ i+1] )

Recherche de la position du minimum « posmin »



3) Activité 3 (Tri par insertion)

a) Principe C’est une méthode de tri qui consiste à prendre les éléments du tableau un par un puis d’insérer chacun

à sa bonne palace façon que les éléments traités forment une liste triée.

Cette méthode peut se traduire par l’algorithme formel suivant :

1- On commence par le deuxième élément,

2- Comparer l’élément choisis avec tous ses précédents dans le tableau et l’insérer dans sa

bonne place,

3- Répéter l’étape 2 pour l’élément suivant jusqu’à arriver au dernier.

b) Algorithme 0) DEF PROC Tri_insertion ( var T :tab ; N : entier)

1) Pour i de 2 à N Faire j i aux T [ i ]

Tant que (j > 1) ET ( T [ j – 1] > aux ) Faire T [ j ] T [ j – 1 ] j j – 1 Fin Tant que

T [ j ] Aux Fin Pour 2) Fin Tri_insertion

II. TRI SHELL a) Principe

- C’est une variante du tri par insertion - Shell propose une suite définie par : U1=1 et Un+1= 3 * Un +1 pour déterminer la valeur du pas. - Trie chaque liste d’éléments séparés par p positions chacun avec un tri par insertion.

b) Exemple T 72 61 44 80 70 85 21 23 51 87 74 94 20 17 56

c) Analyse de la procédure TRI_SHELL

Résultat= T 2) T= [ ] Tant que p>0 faire

P p div 3 Pour i de p à n faire

Aux T[i] J i Tant que (j>p-1) et (T[j-p]>aux) Faire T[j] T[j-p] J j-p Fin Tant que T[j] aux

Fin pour Fin Tant que

1) P=[p0 ] Tant que p<n Faire P 3*p+1

Fin Tant que

Décalage de tous les éléments

supérieurs à aux, «T [ i ]» dans la

liste triée



d) Algorithme

0) DEF PROC TRI_SHELL (var T : tab ; n : entier) 1) P 0

Tant que p<n Faire P 3*p+1

Fin Tant que 2) Tant que p>0 faire

P p div 3 Pour i de p à n faire Aux T[i] J i Tant que (j>p-1) et (T[j-p]>aux) Faire T[j] T[j-p] J j-p Fin Tant que T[j] aux Fin pour Fin Tant que

3) Fin TRI_SHELL

III. Application : TRI PAR FUSION a) principe

- Le tri fusion est construit suivant la stratégie "diviser pour régner".

- Le principe de base de la stratégie "diviser pour régner" est que pour résoudre un gros problème, il est

souvent plus facile de le diviser en petits problèmes élémentaires. Une fois chaque petit problème

résolu, il n’y a plus qu’à combiner les différentes solutions pour résoudre le problème global.

- La méthode "diviser pour régner" est tout à fait applicable au problème de tri : plutôt que de trier le

tableau complet, il est préférable de trier deux sous tableaux de taille égale, puis de fusionner les

résultats.

- L’algorithme de tri par fusion à développer est récursif, En effet, les deux sous tableaux seront eux

même triés à l’aide de l’algorithme de tri fusion. Un tableau ne comportant qu’un seul élément sera

considéré comme trié.

- Etapes de l’algorithme :

Division de l’ensemble de valeurs en deux parties

Tri de chacun des deux ensembles

Fusion des deux ensembles

b) Analyse de la procédure Tri_fusion DEF PROC TRI_FUSION (var T : tab ; d,f : entier) Résultat= TRI_FUSION TRI_FUSION= [ ] SI (d<f) Alors Mil (d+f) div 2 proc tri_fusion (t,d,mil) proc tri_Fusion(t,mil+1,f) proc fusionner(t,d,mil,f) Fin Si



c) Analyse de la procédure Fusionner

DEF PROC FUSIONNER (var T :tab ; d,mil,f :entier) Résultat= T T= [ ] pour i de d à f faire T[i] V[i] Fn pour V= [i d , j mil+1 ] pour k de d à f faire Si (i<=mil) et (t[i] < t[j]) ou (j>f) alors V[k] T[i] i i+1 Sinon V[k] T[j] j j+1 Fin si Fin pour

Documents

Algorithmes de tri