Merge sort est l'un des algorithmes informatiques de base, formulé en 1945 par le grand mathématicien John von Neumann. Lors de sa participation au projet Manhattan, Neumann a été confronté à la nécessité de traiter efficacement d'énormes quantités de données. La méthode qu'il a développée utilisait le principe du "diviser pour mieux régner", ce qui réduisait considérablement le temps nécessaire au travail.
Principe et utilisation de l'algorithme
La méthode de tri par fusion est utilisée dans les problèmes de tri de structures qui ont ordonné l'accès à des éléments, tels que des tableaux, des listes, des flux.
Pendant le traitement, le bloc de données initial est divisé en petits composants, jusqu'à un élément, qui est en fait déjà une liste triée. Ensuite, il est remonté dans le bon ordre.
Le tri d'un tableau d'une certaine longueur nécessite une zone mémoire supplémentaire de même taille, dans laquelle le tableau trié est collecté par parties.
La méthode peut être utilisée pour classer n'importe quel type de données comparable, comme des nombres ou des chaînes.
Fusion triéeparcelles
Pour comprendre l'algorithme, commençons son analyse par la fin - à partir du mécanisme de fusion des blocs triés.
Imaginons que nous ayons deux tableaux de nombres triés de quelque manière que ce soit qui doivent être combinés l'un avec l'autre pour que le tri ne soit pas interrompu. Pour plus de simplicité, nous allons trier les nombres par ordre croissant.
Exemple élémentaire: les deux tableaux sont constitués d'un élément chacun.
int arr1={31}; int arr2={18};
Pour les fusionner, il faut prendre l'élément zéro du premier tableau (n'oubliez pas que la numérotation commence à zéro) et l'élément zéro du second tableau. Ce sont respectivement 31 et 18. Selon la condition de tri, le nombre 18 devrait venir en premier, car il est inférieur. Mettez simplement les chiffres dans le bon ordre:
int résultat={18, 31};
Regardons un exemple plus compliqué, où chaque tableau est composé de plusieurs éléments:
int arr1={2, 17, 19, 45}; int arr2={5, 6, 21, 30};
L'algorithme de fusion consistera à comparer séquentiellement des éléments plus petits et à les placer dans le tableau résultant dans le bon ordre. Pour garder une trace des indices actuels, introduisons deux variables - index1 et index2. Initialement, nous les mettons à zéro, car les tableaux sont triés et les plus petits éléments sont au début.
int index1=0; int index2=0;
Écrivons tout le processus de fusion étape par étape:
- Prenez l'élément avec l'index1 du tableau arr1, et l'élément avec l'index2 du tableau arr2.
- Comparez, sélectionnez le plus petit d'entre eux et inséreztableau résultant.
- Incrémente l'index courant du plus petit élément de 1.
- Continuez depuis la première étape.
Sur la première orbite, la situation ressemblera à ceci:
index1=0; indice2=0; tab1[0]=2; tab2[0]=5; tab1[0] < tab2[0]; indice1++; résultat[0]=tab1[0]; // résultat=[2]
Au deuxième tour:
index1=1; indice2=0; tab1[1]=17; tab2[0]=5; tab1[1] > tab2[0]; index2++; résultat[1]=tab2[0]; // résultat=[2, 5]
Troisième:
index1=1; indice2=1; tab1[1]=17; tab2[1]=6; tableau1[1] > tableau2[1]; index2++; résultat[2]=tab2[1]; // résultat=[2, 5, 6]
Et ainsi de suite, jusqu'à ce que le résultat soit un tableau complètement trié: {2, 5, 6, 17, 21, 19, 30, 45}.
Certaines difficultés peuvent survenir si des tableaux de longueurs différentes sont fusionnés. Que se passe-t-il si l'un des index actuels a atteint le dernier élément et qu'il reste encore des membres dans le deuxième tableau ?
int arr1={1, 4}; int tab2={2, 5, 6, 7, 9}; // 1 pas index1=0, index2=0; 1 2 résultat={1, 2}; // 3 étapes index1=1, index2=1; 4 < 5 résultat={1, 2, 4}; //4 étapes index1=2, index2=1 ??
La variable index1 a atteint la valeur 2, mais le tableau arr1 n'a pas d'élément avec cet index. Tout est simple ici: il suffit de transférer les éléments restants du deuxième tableau vers celui résultant, en préservant leur ordre.
résultat={1, 2, 4, 5, 6, 7, 9};
Cette situation nous indique la nécessitéfaire correspondre l'index de vérification actuel avec la longueur du tableau fusionné.
Schéma de fusion pour les séquences ordonnées (A et B) de longueurs différentes:
- Si la longueur des deux séquences est supérieure à 0, comparez A[0] et B[0] et déplacez la plus petite dans le tampon.
- Si la longueur de l'une des séquences est 0, prenez les éléments restants de la deuxième séquence et, sans changer leur ordre, déplacez-vous à la fin du tampon.
Mise en œuvre de la deuxième étape
Un exemple de jointure de deux tableaux triés en Java est donné ci-dessous.
int a1=nouveau int {21, 23, 24, 40, 75, 76, 78, 77, 900, 2100, 2200, 2300, 2400, 2500}; int a2=nouveau int {10, 11, 41, 50, 65, 86, 98, 101, 190, 1100, 1200, 3000, 5000}; int a3=new int[a1.length + a2.length]; int i=0, j=0; for (int k=0; k a1.length-1) { int a=a2[j]; a3[k]=a; j++; } sinon si (j > a2.length-1) { int a=a1; a3[k]=a; je++; } sinon si (a1 < a2[j]) { int a=a1; a3[k]=a; je++; } sinon { int b=a2[j]; a3[k]=b; j++; } }
Ici:
- a1 et a2 sont les tableaux triés d'origine à fusionner;
- a3 – tableau final;
- i et j sont les index des éléments courants pour les tableaux a1 et a2.
La première et la seconde condition if garantissent que les index ne dépassent pas la taille du tableau. Les troisième et quatrième blocs de condition, respectivement, sont déplacés vers le tableau résultant de l'élément le plus petit.
Diviser pour régner
Donc, nous avons appris à fusionner les triéscollections de valeurs. On peut dire que la deuxième partie de l'algorithme de tri par fusion - la fusion elle-même - a déjà été triée.
Cependant, vous devez toujours comprendre comment passer du tableau de nombres non trié d'origine à plusieurs nombres triés pouvant être fusionnés.
Considérons la première étape de l'algorithme et apprenons à séparer les tableaux.
Ce n'est pas difficile - la liste de valeurs originale est divisée en deux, puis chaque partie est également bifurquée, et ainsi de suite jusqu'à ce que de très petits blocs soient obtenus.
La longueur de ces éléments minimaux peut être égale à un, c'est-à-dire qu'ils peuvent eux-mêmes être un tableau trié, mais ce n'est pas une condition nécessaire. La taille du bloc est déterminée à l'avance, et tout algorithme de tri approprié qui fonctionne efficacement avec des tableaux de petites tailles (par exemple, tri rapide ou tri par insertion) peut être utilisé pour le trier.
Ça ressemble à ça.
// tableau d'origine {34, 95, 10, 2, 102, 70}; // première division {34, 95, 10} et {2, 102, 70}; // seconde division {34} et {95, 10} et {2} et {102, 70}
Les blocs résultants, composés de 1 à 2 éléments, sont très faciles à organiser.
Après cela, vous devez fusionner les petits tableaux déjà triés par paires, en préservant l'ordre des membres, ce que nous avons déjà appris à faire.
Mise en œuvre de la première étape
Le partitionnement récursif d'un tableau est illustré ci-dessous.
void mergeSort(T a, long start, long finish) { long split; si(début < fin) { split=(début + fin)/2; mergeSort(a, start, split); mergeSort(a, split+1, finish); merge(a, start, split, finish); } }
Ce qui se passe dans ce code:
-
La fonction mergeSort récupère le tableau initial
a
et les bordures gauche et droite de la région à trier (indices start et
- finish).
-
Si la longueur de cette section est supérieure à un (
start < finish
), alors elle est divisée en deux parties (par index
- split), et chacun est trié récursivement.
-
Dans l'appel de fonction récursive pour le côté gauche, l'index de départ du tracé et l'index
split
sont passés. Pour la droite, respectivement, le début sera
- (split + 1), et la fin sera le dernier index de la section originale.
-
Function
merge
obtient deux séquences ordonnées (
a[start]…a[split]
et
- a[split +1]…a[finish]) et les fusionne dans l'ordre de tri.
Les mécanismes de la fonction de fusion sont discutés ci-dessus.
Schéma général de l'algorithme
La méthode de tableau de tri par fusion se compose de deux grandes étapes:
- Diviser le tableau d'origine non trié en petits morceaux.
- Rassemblez-les par paires, en suivant la règle de tri.
Une tâche importante et complexe est décomposée en plusieurs tâches simples, qui sont résolues de manière séquentielle, conduisant au résultat souhaité.
Évaluation de la méthode
La complexité temporelle du tri par fusion est déterminée par la hauteur de l'arbre diviséet est égal au nombre d'éléments du tableau (n) multiplié par son logarithme (log n). Une telle estimation est appelée logarithmique.
C'est à la fois un avantage et un inconvénient de la méthode. Son temps d'exécution ne change pas même dans le pire des cas, lorsque le tableau d'origine est trié dans l'ordre inverse. Cependant, lors du traitement de données complètement triées, l'algorithme n'apporte pas de gain de temps.
Il est également important de noter le coût en mémoire de la méthode de tri par fusion. Ils sont égaux à la taille de la collection originale. Dans cette zone supplémentaire allouée, un tableau trié est assemblé à partir des pièces.
Implémentation de l'algorithme
Le tri par fusion Pascal est illustré ci-dessous.
Procedure MergeSort(name: string; var f: text); Var a1, a2, s, i, j, kol, tmp: entier; f1, f2: texte; b: booléen Débutcol:=0; Assign(f, nom); réinitialiser(f); Tant que ce n'est pas EOF(f) commencez read(f, a1); inc(col); finir; fermer(f); Assign(f1, '{nom du 1er fichier auxiliaire}'); Assign(f2, '{nom du 2ème fichier auxiliaire}'); s:=1; Tandis que (s<kol) commencent Reset(f); réécrire(f1); réécrire(f2); For i:=1 to kol div 2 do begin Read(f, a1); Écrire(f1, a1, ' '); finir; Si (kol div 2) mod s0 then begin tmp:=kol div 2; Tandis que tmp mod s0 do begin Read(f, a1); Écrire(f1, a1, ' '); inc(tmp); finir; finir; Tant que ce n'est pas EOF(f), commencez Read(f, a2); Écrire(f2, a2, ' '); finir; fermer(f); fermer(f1); fermer(f2); réécrire(f); réinitialiser(f1); réinitialiser(f2); Lire(f1, a1); Lire(f2, a2); Tandis que (not EOF(f1)) et (not EOF(f2)) commencent i:=0; j=0; b:=vrai; Tandis que (b) et (non EOF(f1)) et (non EOF(f2)) commencent Si (a1<a2) alors commencentÉcrire(f, a1, ' '); Lire(f1, a1); inc(je); Fin sinon début Ecrire(f, a2, ' '); Lire(f2, a2); inc(j); finir; Si (i=s) ou (j=s) alors b:=faux; finir; Si ce n'est pas b, alors commencez While (i<s) et (not EOF(f1)) commencez Write(f, a1, ' '); Lire(f1, a1); inc(je); finir; Tandis que (j<s) et (not EOF(f2)) commencent Write(f, a2, ' '); Lire(f2, a2); inc(j); finir; finir; finir; Tant que ce n'est pas EOF(f1) commencez tmp:=a1; Lire(f1, a1); Si ce n'est pas EOF(f1) alors Write(f, tmp, ' ') else Write(f, tmp); finir; Tant que ce n'est pas EOF(f2) commencez tmp:=a2; Lire(f2, a2); Si ce n'est pas EOF(f2) alors Write(f, tmp, ' ') else Write(f, tmp); finir; fermer(f); fermer(f1); fermer(f2); s:=s2; finir; Effacer(f1); Effacer(f2); Fin;
Visuellement, le fonctionnement de l'algorithme ressemble à ceci (haut - séquence non ordonnée, bas - ordonné).
Tri de données externes
Très souvent, il est nécessaire de trier certaines données situées dans la mémoire externe de l'ordinateur. Dans certains cas, ils sont d'une taille impressionnante et ne peuvent pas être placés en RAM pour faciliter leur accès. Dans de tels cas, des méthodes de tri externes sont utilisées.
Le besoin d'accéder à des supports externes dégrade l'efficacité du temps de traitement.
La complexité du travail est que l'algorithme ne peut accéder qu'à un seul élément du flux de données à la fois. Et dans ce cas, l'un des meilleurs résultats est affiché par la méthode de tri par fusion, qui peut comparer les éléments de deux fichiers séquentiellement l'un après l'autre.
Lecture des données desource externe, leur traitement et leur écriture dans le fichier final sont effectués par blocs ordonnés (séries). Selon la manière de travailler avec la taille des séries ordonnées, il existe deux types de tri: simple et fusion naturelle.
Fusion simple
Avec une simple fusion, la longueur de la série est fixe.
Ainsi, dans le fichier original non trié, toutes les séries sont constituées d'un élément. Après la première étape, la taille passe à deux. Suivant - 4, 8, 16 et ainsi de suite.
Ça marche comme ça:
- Le fichier source (f) est divisé en deux auxiliaires - f1, f2.
- Ils sont à nouveau fusionnés en un seul fichier (f), mais en même temps tous les éléments sont comparés par paires et forment des paires. La taille de la série à cette étape devient deux.
- L'étape 1 est répétée.
- L'étape 2 est répétée, mais les 2 déjà ordonnés sont fusionnés pour former des 4 triés.
- La boucle continue, augmentant la série à chaque itération, jusqu'à ce que tout le fichier soit trié.
Comment savez-vous que le tri externe avec une simple fusion est terminé ?
- longueur de la nouvelle série (après fusion) non inférieure au nombre total d'éléments;
- il ne reste qu'un épisode;
- Le fichier auxiliaire f2 est resté vide.
Les inconvénients d'une fusion simple sont les suivants: étant donné que la longueur d'exécution est fixée à chaque passe de fusion, les données partiellement ordonnées prendront autant de temps à traiter que les données complètement aléatoires.
Fusion naturelle
Cette méthode ne limite pas la longueursérie, mais choisit le maximum possible.
Algorithme de tri:
- Lecture de la séquence initiale du fichier f. Le premier élément reçu est écrit dans le fichier f1.
- Si la prochaine entrée satisfait la condition de tri, elle y est écrite, sinon, alors dans le deuxième fichier auxiliaire f2.
- De cette manière, tous les enregistrements du fichier source sont distribués et une séquence ordonnée est formée en f1, qui détermine la taille actuelle de la série.
- Les fichiers f1 et f2 sont fusionnés.
- Le cycle se répète.
En raison de la taille non fixe de la série, il est nécessaire de marquer la fin de la séquence avec un caractère spécial. Par conséquent, lors de la fusion, le nombre de comparaisons augmente. De plus, la taille de l'un des fichiers auxiliaires peut être proche de la taille de l'original.
En moyenne, la fusion naturelle est plus efficace que la simple fusion avec tri externe.
Caractéristiques de l'algorithme
Lors de la comparaison de deux valeurs identiques, la méthode préserve leur ordre d'origine, c'est-à-dire qu'elle est stable.
Le processus de tri peut être très bien divisé en plusieurs threads.
La vidéo montre clairement le fonctionnement de l'algorithme de tri par fusion.
