algorithme de tri par fusion

Do you want to read our courses in English? please visit our new website cs-teachers.com Click here

algorithme de tri par fusion

Le tri par fusion est l'un des algorithmes de tri les plus populaires et les plus efficaces. Et il est basé sur le paradigme Diviser pour régner.

Exemple :

Stratégie

En utilisant la technique Diviser pour régner, nous divisons un problème en sous-problèmes. Lorsque la solution à chaque sous-problème est prête, nous «combinons» les résultats des sous-problèmes pour résoudre le problème principal.

Supposons que nous devions trier un tableau T. Un sous-problème serait de trier une sous-section (sous-tableau) de ce tableau commençant à l'indice debut et se terminant à l'indice fin, notée T[debut..fin].

Un algorithme typique de Diviser pour régner résout un problème en utilisant les trois étapes suivantes :

Diviser

Si milieu est le point milieu entre debut et fin, alors nous pouvons diviser le sous-tableau T[debut..fin] en deux tableaux T[debut..milieu] et T[milieu + 1, fin].

Régner/Résoudre

Dans l'étape Régner, nous essayons de trier les sous-réseaux T[debut..milieu] et T[milieu + 1, fin]. Si nous n'avons pas encore atteint le cas de base (le sous-tableau contient un seul élément), nous divisons à nouveau ces deux sous-réseaux et essayons de les trier.

Combiner

Lorsque l'étape de conquête atteint l'étape de base et que nous obtenons deux sous-tableaux triés T[debut..milieu] et T[milieu + 1, fin] pour le tableau T[debut..milieu], nous combinons les résultats en créant un tableau trié T[debut..milieu] à partir de deux sous-réseaux triés T[debut..milieu] et T[milieu + 1, fin].

Algorithme

La fonction triFusion divise à plusieurs reprises le tableau en deux moitiés (deux sous-tableaux) jusqu'à ce que nous atteignions un stade où nous essayons d'effectuer triFusion sur un sous-tableau de taille 1, c'est-à-dire debut == fin.

Après cela, la fonction de fusion entre en jeu et combine les tableaux triés dans un tableau plus grand jusqu'à ce que l'ensemble du tableau soit fusionné.

fonction triFusion(T, debut, fin):
    Si debut > fin alors
        retourne
    
    # Trouvez le point milieu pour diviser le tableau en deux moitiés
    milieu = (debut+fin)/2
    
    # Appelez triFusion pour la première moitié du tableau:
    triFusion(T, debut, milieu)

    # Appelez triFusion pour la deuxième moitié du tableau:
    triFusion(T, milieu+1, fin)

    # Fusionnez les deux moitiés triées
    fusion(T, debut, fin, milieu)
                            

Comme le montre l'image ci-dessus, l'algorithme de tri par fusion divise récursivement le tableau en deux jusqu'à ce que nous atteignions le cas de base d'un tableau avec 1 élément. Après cela, la fonction de fusion récupère les sous-tableaux triés et les fusionne pour trier progressivement l'ensemble du tableau.

Comme vous pouvez le voir, la fonction la plus importante dans le tri par fusion est la fusion de fonctions. Ensuite, nous discuterons plus en détail cette fonction

Fonction fusion

L'étape de fusion est la solution au problème simple de fusion de deux listes triées (tableaux) pour créer une grande liste triée (tableau).

L'algorithme maintient trois pointeurs, un pour chacun des deux tableaux et un pour maintenir l'index actuel du tableau trié final.

                                Est-ce que nous avon atteint la fin de l'un des tableaux?
                                    -> Non
                                            - Comparer les éléments actuels des deux tableaux (T1[i] et T2[j])
                                            - Copiez l'élément le plus petit dans le tableau trié
                                            - Déplacer le pointeur de l'élément contenant un élément plus petit (i ou j)
                                    -> Oui
                                            - Copiez tous les éléments restants du tableau non vide
                            
Exemple :

Implémentation

                                            class Test {

                                                void fusion(int tab[], int debut, int milieu, int fin) {
                                                    int n1 = milieu - debut + 1;
                                                    int n2 = fin - milieu;
                                            
                                                    int G[] = new int[n1];
                                                    int D[] = new int[n2];
                                            
                                                    for (int i = 0; i < n1; i++)
                                                        G[i] = tab[debut + i];
                                                    for (int j = 0; j < n2; j++)
                                                        D[j] = tab[milieu + 1 + j];
                                            
                                                    // maintient trois pointeurs, un pour chacun des deux tableaux et un pour
                                                    // maintenir l'index actuel du tableau trié final
                                                    int i, j, k;
                                                    i = 0;
                                                    j = 0;
                                                    k = debut;
                                            
                                                    while (i < n1 && j < n2) {
                                                        if (G[i] <= D[j]) {
                                                            tab[k] = G[i];
                                                            i++;
                                                        } else {
                                                            tab[k] = D[j];
                                                            j++;
                                                        }
                                                        k++;
                                                    }
                                            
                                                    // Copiez tous les éléments restants du tableau non vide
                                                    while (i < n1) {
                                                        tab[k] = G[i];
                                                        i++;
                                                        k++;
                                                    }
                                            
                                                    while (j < n2) {
                                                        tab[k] = D[j];
                                                        j++;
                                                        k++;
                                                    }
                                                }
                                            
                                                // Tri par fusion
                                                void triFusion(int tab[], int debut, int fin) {
                                                    if (debut < fin) {
                                            
                                                        // Trouvez le point milieu pour diviser le tableau en deux moitiés
                                                        int m = (debut + fin) / 2;
                                            
                                                        triFusion(tab, debut, m);
                                                        triFusion(tab, m + 1, fin);
                                            
                                                        // Fusionnez les deux moitiés triées
                                                        fusion(tab, debut, m, fin);
                                                    }
                                                }
                                            
                                                public static void main(String args[]) {
                                                    int tab[] = { 64, 25, 12, 22, 11 };
                                            
                                                    Test ob = new Test();
                                                    ob.triFusion(tab, 0, tab.length - 1);
                                                }
                                            }
                                        
                                            #include <stdio.h>

                                                void fusion(int tab[], int debut, int milieu, int fin)
                                                {
                                                    int n1 = milieu - debut + 1;
                                                    int n2 = fin - milieu;
                                                
                                                    int G[n1], D[n2];
                                                
                                                    for (int i = 0; i < n1; i++)
                                                        G[i] = tab[debut + i];
                                                    for (int j = 0; j < n2; j++)
                                                        D[j] = tab[milieu + 1 + j];
                                                
                                                    // maintient trois pointeurs, un pour chacun des deux tableaux et un pour
                                                    // maintenir l'index actuel du tableau trié final
                                                    int i, j, k;
                                                    i = 0;
                                                    j = 0;
                                                    k = debut;
                                                
                                                    while (i < n1 && j < n2)
                                                    {
                                                        if (G[i] <= D[j])
                                                        {
                                                            tab[k] = G[i];
                                                            i++;
                                                        }
                                                        else
                                                        {
                                                            tab[k] = D[j];
                                                            j++;
                                                        }
                                                        k++;
                                                    }
                                                
                                                    // Copiez tous les éléments restants du tableau non vide
                                                    while (i < n1)
                                                    {
                                                        tab[k] = G[i];
                                                        i++;
                                                        k++;
                                                    }
                                                
                                                    while (j < n2)
                                                    {
                                                        tab[k] = D[j];
                                                        j++;
                                                        k++;
                                                    }
                                                }
                                                
                                                // Tri par fusion
                                                void triFusion(int tab[], int debut, int fin)
                                                {
                                                    if (debut < fin)
                                                    {
                                                
                                                        // Trouvez le point milieu pour diviser le tableau en deux moitiés
                                                        int m = (debut + fin) / 2;
                                                
                                                        triFusion(tab, debut, m);
                                                        triFusion(tab, m + 1, fin);
                                                
                                                        // Fusionnez les deux moitiés triées
                                                        fusion(tab, debut, m, fin);
                                                    }
                                                }
                                                
                                                void afficher(int tab[], int n)
                                                {
                                                    for (int i = 0; i < n; i++)
                                                        printf("%d ", tab[i]);
                                                    printf("\n");
                                                }
                                                
                                                
                                                int main()
                                                {
                                                    int tab[] = {64, 25, 12, 22, 11};
                                                    int n = 5;
                                                
                                                    triFusion(tab, 0, n - 1);
                                                
                                                    printf("Tableau trié: \n");
                                                    afficher(tab, n);
                                                }
                                        
def triFusion(tab):
    if len(tab) > 1:
        mid = len(tab)//2

        G = tab[:mid] # sous-tableau gauche
        D = tab[mid:] # sous-tableau droit

        triFusion(G)
        triFusion(D)

        # Fusion                               
        i = j = k = 0

        while i < len(G) and j < len(D):
            if G[i] < D[j]:
                tab[k] = G[i]
                i += 1
            else:
                tab[k] = D[j]
                j += 1
            k += 1

        while i < len(G):
            tab[k] = G[i]
            i += 1
            k += 1

        while j < len(D):
            tab[k] = D[j]
            j += 1
            k += 1


A = [64, 25, 12, 22, 11]
triFusion(A)
print("Voici le tableau trié")
for i in range(len(A)):
    print("%d" % A[i]),
                                        

Le tri par fusion est un algorithme récursif et la complexité temporelle peut être exprimée comme une relation de récurrence. $$ T(n)=2T(\frac{n}{2}) + \Theta(n) $$

La récurrence ci-dessus peut être résolue en utilisant la méthode de l'arbre de récurrence ou la théorème principale (Master theorem). la solution de la récurrence est $$ T(n)=\Theta(nlog n) $$

La complexité temporelle du tri par fusion est \(\Theta (nLogn)\) dans les 3 cas (pire, moyen et meilleur) car le tri par fusion divise toujours le tableau en deux moitiés et prend un temps linéaire pour fusionner deux moitiés.

Partager ce cours avec tes amis :

Rédigé par ESSADDOUKI Mostafa

The education of the 21st century opens up opportunities to not merely teach, but to coach, mentor, nurture and inspire.

Commentaire(s)