ASD3_23/24: les algorithmes de tri -2 -

2-tri à bulle:

Principe :

Le principe du tri à bulles (bubble sort) est de comparer deux à deux les éléments j-1 et j consécutifs d'un tableau et d'effecteur une permutation si t[j-1] > t[j] .

L’algorithme recommence l’opération. Lorsqu’aucune permutation n’a lieu pendant un parcours, cela signifie que le tableau est trié. On arrête alors l’algorithme.

l'algorithme :

procedure tri_a_bulle(var T:tableau)

var  i;j;n;temp:entier;

Debut
Pour i ← 1  à n-1 fairePour  j ← n  à i+1
Si t[j-1]>t[j]  Alors
                 temp←t[j-1];

                 t[j-1]←t[j];

                    t[j]←temp;
fsi
fpour
fpour
Fin;
Exemple :

3-Tri par insertion :
Principe :
On insère (au i ème itération) le ième élément T[i] à la bonne place parmi T[1],T[2]...T[i-1].
• Après l'étape i, tous les éléments entre la première et la ième position sont triés.
• Pour tout nouvel élément, trouver sa position et l’insérer
Algorithme :
Procedure tri_insertion(var t:tableau)
var i,j,x,n : entier;
Debut

pour  i de 1  à  n faire
x←T[i];
j←i;
tant  que ( T[j-1]  >  x  et j >1)
       T[j]←T[j-1]
       j ←j–1
Fin  TantQue

T[j]←x;
Fin  Pour

fin;

Exemple :

4- le tri par fusion :
tri par fusion est un algorithme de tri sur la base de comparaisons qui utilisent un processus de règlement récursif, en exploitant la technique de divisier et rogner, qui consiste à diviser le problème en sous-problèmes de même nature de la taille de plus en plus petit. I
Principe de fonctionnement :

On divise en deux moitiés la liste à trier (en prenant par exemple, un élément sur deux pour chacune des listes).
On trie chacune d’entre elles.
On fusionne les deux moitiés obtenues pour reconstituer la liste triée.

Le travail demandé :
Etudier la complexité des algorithmes de tri vues en cours.

Modifié le: vendredi 18 novembre 2022, 14:53