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 :
