Tri fusion
Un article de Freepedia.
Le tri fusion est un algorithme de tri optimal (complexité en <math>\Theta(n \log n)</math> et consomme n en mémoire).
Le tri repose sur le fait que pour fusionner deux listes/tableaux trié(e)s, n comparaisons (au maximum) sont nécessaires.
Sommaire |
Exemple
Opération de fusion
Fusionner [1;2;5] et [3;4] : On sait que le premier élément de la liste fusionnée sera le premier élément d'une des deux listes d'entrée (soit 1, soit 3), propriété non remarquable sur des listes non triées.
On compare donc 1 et 3 → 1 est plus petit.
[2;5] - [3;4] → [1]
On compare 2 et 3 → 2 est plus petit.
[5] - [3;4] → [1;2]
On compare 5 et 3 → 3 est plus petit.
[5] - [4] → [1;2;3]
On compare 5 et 4 → 4 est plus petit.
[5] → [1;2;3;4]
[1;2;3;4;5]
Bien sûr ce n'est qu'une étape du tri.
Tri, procedure complète
À l'état initial on a les éléments un par un, on les fusionne deux a deux:
([6] [1]) ([2] [5]) ([4] [7]) [3]
On obtient:
([1;6] [2;5]) ([4;7] [3]) que l'on fusionne deux à deux à nouveau et ainsi de suite:
([1;2;5;6] [3;4;7])
[1;2;3;4;5;6;7]
Remarque : On fait <math>\log n</math> operations de fusion, ici on à 7 éléments, on fait 3 fusions (nécessitant chacune n comparaisons, soit <math>n \log n</math>). c
Propriétés
- Le nombre de comparaisons nécessaires est de l'ordre de <math>n \log n</math>.
- L'espace mémoire requis est de n.
Implémentations
Une mise en œuvre simple du tri par insertion sur un tableau d'entiers en C :
typedef int tab_entiers[MAX];
void fusionrec(tab_entiers t, tab_entiers tmp, int de1, int vers1, int de2, int vers2, int count, int posInB) {
int i;
for(i = 0 ; i < count ; i++) {
if(de2 > vers2 - 1) tmp[posInB++] = t[de1++];
else if(de1 > vers1) tmp[posInB++] = t[de2++];
else if(t[de1] < t[de2]) tmp[posInB++] = t[de1++];
else tmp[posInB++] = t[de2++];
}
}
void fusion(tab_entiers t) {
tab_entiers tmp;
int sortLength = 1, de1, de2, vers1, vers2, i;
while(sortLength < MAX) {
de1 = 0;
while(de1 < MAX) {
de2 = de1 + sortLength;
vers1 = de2 - 1;
vers2 = de2 + sortLength - 1;
if(vers1 >= MAX - 1) fusionrec(t, tmp, de1, MAX-1, 0, 0, MAX-de1, de1);
else if (vers2 >= MAX - 1) fusionrec(t, tmp, de1, vers1, de2, MAX, MAX-de1, de1);
else fusionrec(t, tmp, de1, vers1, de2, vers2 + 1, 2*sortLength, de1);
de1 = vers2 + 1;
}
for(i = 0 ; i < MAX ; i++) t[i] = tmp[i];
sortLength *= 2;
}
}
