Le Tri Fusion (Merge Sort) en C

## Le tri fusion (merge sort) est un algorithme de tri efficace qui utilise la technique "diviser pour régner". L'idée principale est de diviser récursivement le tableau en deux sous-tableaux jusqu'à ce que chaque sous-tableau ait un seul élément, puis de fusionner ces sous-tableaux de manière à les trier.

1. Principe du tri fusion

Le tri fusion fonctionne selon ces étapes :

1. Diviser le tableau en deux moitiés jusqu'à obtenir des sous-tableaux de taille 1 (qui sont, par définition, triés).
2. Fusionner les deux moitiés triées pour former un seul tableau trié. Pour cela, on compare les éléments des deux sous-tableaux et on les insère dans un tableau temporaire dans l'ordre croissant.

2. Fonctions dans le tri fusion

1. Fonction principale (tri_fusion) : Cette fonction divise le tableau en deux sous-tableaux et appelle la fonction fusionner pour les assembler dans un tableau trié.
2. Fonction de fusion (fusionner) : Cette fonction prend deux sous-tableaux triés et les fusionne en un seul tableau trié.

3. Code en C avec commentaires

// Code en C du tri fusion avec des variables en français
#include <stdio.h>
#include <stdlib.h>

// Fonction de fusion qui fusionne deux sous-tableaux (gauche et droite)
void fusionner(int tab[], int deb, int mil, int fin) {
    // ng = nombre d'éléments dans le tableau de gauche
    int ng = mil - deb + 1;
    // nd = nombre d'éléments dans le tableau de droite
    int nd = fin - mil;

    // Tableaux temporaires pour stocker les parties gauche et droite
    int tg[ng], td[nd];

    // Copier les éléments dans le tableau gauche tg
    for (int i = 0; i < ng; i++)
        tg[i] = tab[deb + i];

    // Copier les éléments dans le tableau droit td
    for (int j = 0; j < nd; j++)
        td[j] = tab[mil + 1 + j];

    // Indices initiaux des sous-tableaux et du tableau fusionné
    int i = 0, j = 0, k = deb;

    // Fusionner les tableaux tg et td dans tab[]
    while (i < ng && j < nd) {
        if (tg[i] <= td[j]) {
            tab[k] = tg[i];
            i++;
        } else {
            tab[k] = td[j];
            j++;
        }
        k++;
    }

    // Copier le reste des éléments de tg (s'il en reste)
    while (i < ng) {
        tab[k] = tg[i];
        i++;
        k++;
    }

    // Copier le reste des éléments de td (s'il en reste)
    while (j < nd) {
        tab[k] = td[j];
        j++;
        k++;
    }
}

// Fonction récursive qui divise le tableau et appelle la fusion
void tri_fusion(int tab[], int deb, int fin) {
    if (deb < fin) {
        // Calcul de l'indice du milieu
        int mil = (deb + fin) / 2;

        // Appel récursif pour diviser la partie gauche
        tri_fusion(tab, deb, mil);

        // Appel récursif pour diviser la partie droite
        tri_fusion(tab, mil + 1, fin);

        // Fusionner les deux moitiés triées
        fusionner(tab, deb, mil, fin);
    }
}

// Fonction pour afficher le tableau
void afficher_tableau(int tab[], int taille) {
    for (int i = 0; i < taille; i++)
        printf("%d ", tab[i]);
    printf("\n");
}

// Fonction principale
int main() {
    // Déclaration du tableau
    int tab[] = {38, 27, 43, 3, 9, 82, 10};
    
    // Taille du tableau
    int taille = sizeof(tab) / sizeof(tab[0]);

    // Affichage du tableau avant le tri
    printf("Tableau avant tri :\n");
    afficher_tableau(tab, taille);

    // Tri fusion
    tri_fusion(tab, 0, taille - 1);

    // Affichage du tableau après le tri
    printf("Tableau après tri :\n");
    afficher_tableau(tab, taille);

    return 0;
}
        

4. on essaie de comprendre le code

1. fusionner

Cette fonction fusionne deux sous-tableaux triés. Les tableaux tg et td représentent respectivement les parties gauche et droite du tableau original. La boucle principale compare les éléments des deux sous-tableaux et les insère dans le tableau original dans l'ordre croissant. Après la fin de la boucle, s'il reste des éléments non traités dans l'un des sous-tableaux, ils sont copiés dans le tableau final.

2. tri_fusion

Cette fonction est appelée récursivement. Elle divise le tableau en deux jusqu'à atteindre des sous-tableaux de taille 1. Une fois les deux moitiés triées, elles sont fusionnées en appelant la fonction fusionner.

3. Fonction d'affichage

Simple fonction qui permet d'afficher les éléments du tableau avant et après le tri pour vérifier les résultats.

5. les variables ?

• deb : Indice de début du tableau ou sous-tableau.
• fin : Indice de fin du tableau ou sous-tableau.
• mil : Indice du milieu du tableau, utilisé pour diviser le tableau en deux parties.
• tg : Tableau temporaire représentant la partie gauche.
• td : Tableau temporaire représentant la partie droite.

6. Complexité de l'algorithme

Complexité temporelle : Le tri fusion a une complexité de O(n log n), où n est le nombre d'éléments du tableau. Cela est dû au fait que le tableau est divisé en deux à chaque étape (log n) et que chaque fusion prend un temps linéaire (O(n)).

Complexité spatiale : Le tri fusion utilise un espace supplémentaire pour stocker les sous-tableaux, donc sa complexité spatiale est de O(n).

Conclusion

Le tri fusion est un algorithme efficace pour trier de grands tableaux. Il utilise une approche récursive et divise le tableau en plus petites parties pour faciliter le tri, puis les fusionne pour obtenir un tableau entièrement trié.