Algorithmes de tri
Quelques méthodes
* On souhaite trier n éléments d'un tableau t
* Supposons par ordre croissant
* Méthode 1: tri par sélection
* Approche très simple
* Double parcours du tableau
* Méthode 2: tri par fusion
* Approche plus efficace
* Algorithme récursif
* Il en existe d'autres
Tri par sélection (1/3)
* Principe: permuter les éléments deux-à-deux
* S'ils ne respectent pas l'ordre de tri
* Comparaison de deux éléments
* Soit i et j deux indices dans le tableau
* Supposons i < j
* Si t[j] < t[i] ==> permutation t[i] ? t[j]
* On parcours donc tout le tableau ==> indice i
* L'indice i pointe successivement chaque élément du tableau
* A partir de i, on parcours le reste du tableau ==> indice j
* Si t[j] < t[i] ==> permutation des éléments
Tri par sélection (2/3)
Tri par sélection (3/3)
fonction trierSelection(Element * t, int n):
i = 0;
tant que (i < n - 1) faire
j = i + 1;
tant que (j < n) faire
si (t[j] < t[i]) alors
tmp = t[j];
t[j] = t[i];
t[i] = tmp;
fin si
j = j + 1;
fin tant que
i = i + 1;
fin tant que
fin fonction
Tri par fusion (1/3)
* Principe: diviser pour régner ("divide and conquer")
* On divise le tableau en deux ==> t1 et t2
* On tri les deux sous-tableaux
* On fusionne les sous-tableaux triés
* Tri des sous-tableaux
* Appel récursif: t1 et t2 sont eux-mêmes divisés
* Fusion des sous-tableaux
* Parcours simultané de t1 et t2 ==> indices i et j
* Si t1[i] ? t2[j] ==> on récupère t1[i] et incrémentation i
* Si t1[i] > t2[j] ==> on récupère t2[j] et incrémentation j
Tri par fusion (2/3)
Tri par fusion (3/3)
fonction trierFusion(Element * t, int n):
si (n > 1) alors
n1 = ? n / 2 ?;
n2 = n - n1;
t1 = ALLOUER(int,n1); // Allocation tableau de n1 entiers
t2 = ALLOUER(int,n2); // Allocation tableau de n2 entiers
scinder(t,t1,n1,t2,n2); // Scission (copie des éléments) de t dans t1 et t2
trierFusion(t1,n1); // Appel récursif
trierFusion(t2,n2); // Appel récursif
fusionner(t,t1,n1,t2,n2); // Fusion des tableaux triés t1 et t2 dans t
LIBERER(t1); // Libération tableau t1
LIBERER(t2); // Libération tableau t2
fin si
fin fonction