Fusionner le tri en c
Le programme Mergesort, écrit normalement, est comparable (en termes de vitesse) à la fonction tri () fournis par C ++ dans sa bibliothèque d'algorithme. Merge-Sort est également un programme commercial à usage général.
Cet article explique comment rédiger le programme Mergesort dans la langue C.
Algorithme de division et de conquis, au sens large
Dans son sens large, le tableau d'éléments est divisé en deux moitiés: la moitié gauche et la moitié droite. Si le nombre total d'éléments à tri est étrange, alors la moitié gauche est agrandie que la moitié droite, par 1 unité. Sinon, les deux moitiés sont de la même longueur. Les deux moitiés sont ensuite fusionnées lors du tri pour former un tableau trié. La fusion / tri est conquérante. Considérez les personnages suivants à tri:
Q w e r t y u i o pDiviser cet ensemble de caractères alphabétiques en deux moitiés, donne:
Q w e r t y u i o pUn sous-tableau est appelé une course. Ainsi, le sous-tableau gauche, «Q w e r t» est une course et le sous-tableau droit, «Y u i o p» est également une course. Une course ne peut également avoir qu'un seul élément.
La fusion / tri (conquérir) les deux moitié en un seul ensemble donne:
E i o p q r t u w yLe code à diviser par 2 est:
int imiddle = (ibegin + iend) / 2;C'est une division entière. Ainsi, la partie du nombre entier du résultat est prise. Avec cela, si le nombre total d'éléments dans l'ensemble est impair, la moitié gauche serait plus grande que la moitié droite, par 1 unité pour l'indexation zéro.
Pour l'instruction ci-dessus et l'ensemble, 'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p', ibegin = 0, iend = 10 (qui est le dernier indice de 9, plus 1), imiddle = 5;
Le code à fusionner / trier (conquérir) est:
int i = ibegin;int j = imiddle;
pour (int k = ibegin; k
Q [k] = p [i];
i = i + 1;
autre
Q [k] = p [j];
J = J + 1;
P est le tableau donné. Q aurait le tableau trié, dans ce cas.
Si ce code est appliqué à l'ensemble, 'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p' , il y aura de la fusion des moitiés divisées, mais pas de tri (car chaque élément de la course gauche est inférieur à «y»). Ce code est revisité ci-dessous pour montrer son efficacité dans le tri d'une paire de courses consécutives.
Algorithme de division et de conquête pratique
L'ensemble du programme Mergesort peut être écrit de haut en bas ou de bas en haut. Dans cet article, le programme est écrit, de haut en bas.
Un Mergesort fonctionne conceptuellement de la manière suivante:
1) Divisez l'ensemble non trié en n sous-ensembles (exécutions), où chacun a un élément. Notez qu'un ensemble avec un seul élément est considéré comme trié.
2) fusionner à plusieurs reprises des sous-ensembles pour obtenir de nouveaux sous-ensembles triés, jusqu'à ce qu'un seul sous-ensemble soit laissé. C'est l'ensemble trié.
Avec ces deux points, un ensemble non trié donné est divisé en deux courses. Chacune de ces deux analyses est enregistrée en mémoire pour fusionner / tri ensemble, mais non fusionnée ou triée. Chaque course à nouveau de chaque côté, est divisée en deux. Les paires de courses consécutives sont enregistrées pour fusionner / tri ensemble, mais pas encore fusionnée ou trie. Cette division en deux et l'enregistrement pour fusion / tri des paires consécutives sont répétées jusqu'à ce qu'il n'y ait qu'un seul élément par course.
L'enregistrement en mémoire pour fusionner / tri ensemble de cycles consécutifs est effectué en appelant le code de tri ci-dessus récursivement après la division. Le code de tri est dans une fonction séparée. L'instruction de division et l'appel de la fonction de tri (qui fait également fusion) se trouve dans un segment de code (une fonction) avec l'instruction de division tapée d'abord.
Lorsque la division a atteint l'état des exécutions d'un seul élément, les fonctions de fusion / tri enregistrées en mémoire sont appelées dans l'ordre inverse dans lequel ils ont été enregistrés. Il s'agit d'une fonction fusion / tri qui a été enregistrée en mémoire plusieurs fois avec différents arguments. Les paires consécutives d'éléments simples sont triées pour la première fois, fusionnant en même temps. Le tri et la fusion des courses consécutives se poursuivent jusqu'à ce que l'ensemble soit trié. Donc, le tri n'est pas vraiment sur la disposition des éléments tels que donnés à l'origine.
En C, il y a un besoin d'un deuxième tableau, dont la longueur est aussi longue que le tableau donné. Initialement, tous les éléments de ce deuxième tableau doivent être faits, la valeur par défaut du type de données. Les éléments du tableau donné sont triés dans ce deuxième tableau. Puis a copié dans le tableau donné, passant les éléments non triés.
Pour les caractères, ce deuxième tableau peut être créé et initialisé comme suit:
char p [] = 'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p';int sz = sizeof (p) / sizeof (p [0]);
char q [sz];
pour (int i = 0; i
Ici, le tableau donné est P, et le deuxième tableau est Q. Ce code peut être dans la fonction principale. En C / C ++, le caractère par défaut est "et non un espace ("). Cependant, comme le compilateur G ++ n'autoriserait pas l'affectation de "à Q [i], l'espace unique ("), a été attribué.
Notez que les valeurs par défaut pour les éléments du tableau Q ne sont pas vraiment nécessaires pour le programme complet de Mergesort car ils seront toujours remplacés par les éléments d'intérêt. DÉCLARATION DE LA TABLEAT Q Avec sa taille, SZ suffit.
L'ensemble, 'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p', est utilisé pour expliquer comment Mergesort est réalisé pratiquement, dans cette section. Donner des valeurs par défaut du tableau Q a été enseignée dans cet article sous forme de connaissances supplémentaires.
L'ensemble est divisé en deux ensembles:
'Q', 'w', 'e', 'r', 't' et 'y', 'u', 'i', 'o', 'p'Le code de fusion / tri ci-dessus est appelé en fonction mais le tri et la fusion ne se produisent pas. Dans le programme réel, le tri et la fusion de ces deux analyses sont enregistrés en mémoire, d'abord. Le tri et la fusion ne seront finalement pas nécessairement effectués sur ces deux arrangements particuliers de personnages.
Les deux sous-ensembles ci-dessus sont chacun, divisés en deux pour avoir:
'Q', 'w', 'e' et 'r', 't' et 'y', 'u', 'i' et 'o', 'p'Notez que pour chaque nouvelle division ici, le sous-ensemble gauche est plus long que le sous-ensemble droit d'une unité.
Le code de fusion / tri ci-dessus est appelé en fonction, pour des paires consécutives de ces nouveaux sous-ensembles. Mais le tri et la fusion ne se déroulent pas immédiatement. Le tri et la fusion de ces paires de courses consécutives sont enregistrées dans la mémoire de l'ordinateur. Le tri et la fusion ne seront finalement pas nécessairement faits, sur la disposition particulière des personnages de ces paires de courses consécutives.
Les sous-ensembles ci-dessus sont chacun, divisés en deux pour avoir:
'Q', 'w' et 'e' et 'r' et 't' et 'y', 'u' et 'i' et 'o' et 'P'Le tri et la fusion de paires consécutives sont enregistrées.
Ici, certains sous-ensembles ne peuvent plus être divisés car ils se compose chacun d'un élément. Ensuite, la division des sous-ensembles de plus d'une longueur ci-dessus, conduit à:
'Q' et 'w' et 'e' et 'r' et 't' et 'y' et 'u' et 'i' et ' O ' et ' p 'Le tri et la fusion de paires consécutives sont enregistrées.
La fonction de tri et de fusion est codée de manière récursive. Et donc, il sera appelé dans l'ordre inversé, pour les nombreuses fois, il a été enregistré.
Ainsi, 'q' et 'w' sera trié et fusionné dans 'q', 'w'. 'E' et 'r' seront triés et fusionnés en 'e', 'r'. 'T'. 'Y' sera trié et fusionné dans 't', 'y'. 'U' et 'i' seront triés et fusionnés dans 'i', 'u'. 'O'. 'P' sera trié et fusionné dans 'o', 'p'. La fonction de fusion et de tri ci-dessus est utilisée ici; Et il est utilisé tout au long.
Suivant: 'q', 'w' et 'e', 'r' sera trié et fusionné dans 'e', 'q', 'r', 'w'. 'T', 'y' et 'i', 'u' sera trié et fusionné dans, 'i', 't', 'u', 'y'. À ce stade, 'o', 'p' n'est joint à aucun sous-ensemble précédent de deux. La fonction de fusion et de tri ci-dessus a été utilisée ici et est utilisée tout au long.
L'étape suivante: 'e', 'q', 'r', 'w' et 'i', 't', 'u', 'y' sont triées et fusionnées dans 'e', ' I ',' q ',' r ',' t ',' u ',' w ',' y '. À ce stade, 'o', 'p' n'est à nouveau joint à aucun des sous-ensembles précédents.
La dernière étape: 'e', 'i', 'q', 'r', 't', 'u', 'w', 'y' et 'o', p ' sont triées et fusionnées dans 'e', 'i', 'o', 'p', 'q', 'r', 't', 'u', 'w', 'y'. L'ensemble non trié a été trié.
Codage mersort en c
La tâche consiste à trier le tableau P et non le tableau Q. Ainsi, pour l'ensemble du programme Mergesort, le tableau Q est d'abord fait une copie de la table P. Le programme trie ensuite le tableau Q dans le tableau P. Ce n'est pas tout à fait ce qui est insinué ci-dessus. Il existe quatre fonctions pour le programme complet de Mergesort.
La fonction pour diviser et fusionner
Ceci est la fonction principale du programme. Rappelons que la fusion implique également le tri des courses consécutives gauche et droite. Cette fusion est en mémoire et commence réellement lorsque le tableau a été divisé par deux et deux et deux, etc. Jusqu'à ce qu'il n'y ait qu'un seul élément par course. Donc, le tri et la fusion commencent à ce stade avec une paire pour un élément par course. Le squelette de la fonction de tri est:
void topdownSplitmerge (char q [], int ibegin, int iend, char p [])| |
// Divisez le sous-ensemble plus de 1 élément en deux
int imiddle = (ibegin + iend) / 2; // imiddle est le point médian
| |
| |
| |
// fusionner les sous-ensembles résultants du tableau Q [] en p []
TopdownMerge (q, ibegin, imiddle, iend, p);
Cette fonction prend le tableau donné comme q qui, dans ce cas, est en fait le tableau de copie q. Il prend également le tableau de copie comme P qui, dans ce cas, est en fait le tableau donné P. Pour le premier appel de cette fonction, ibegin = 0 et iend = n, où n est la taille des deux tableaux. Ce sont à cause de l'emploi zéro indexé du tableau.
Après une division par deux, Ibegin sera le premier index de la course gauche et Iend sera le dernier index de la course droite consécutive. La division par deux donne à l'imiddle entier, ignorant le reste. Ceci est le dernier index de l'exécution de gauche et aussi le premier index de l'exécution droite. Cette ambiguïté est éliminée par la condition de la condition du code de tri.
La dernière instruction du code ci-dessus est un appel à la fonction de fusion et de tri précise. Cet appel va à la mémoire, lorsqu'il est appelé. Il sera exécuté dans l'ordre inversé pour tous ses appels car il s'agit d'un appel récursif. Il prend les variables comme arguments. Q, ibegin, iend et p, reçu par la fonction codée extérieure. Imiddle, qui est également l'un de ses arguments, est créé à l'intérieur de la fonction codée extérieure, au-dessus de l'appel.
C'est à l'intérieur de cette fonction codée extérieure que les exécutions gauche et droite doivent être identifiées (divisées). Cela est mieux fait en faisant un appel récursif à la fonction codée extérieure comme suit (un code inclus dans la définition de la fonction):
void topdownSplitmerge (char q [], int ibegin, int iend, char p [])// Divisez le sous-ensemble plus de 1 élément en deux
int imiddle = (ibegin + iend) / 2; // imiddle est le point médian
// Trier récursivement les deux courent du tableau a [] en b []
TopdownSplitMerge (p, ibegin, imiddle, q); // Divisez le sous-ensemble gauche en deux pour le tri, après la mémorisation
TopdownSplitmerge (p, imiddle, iend, q); // Divisez le sous-ensemble droit en deux pour le tri, après la mémorisation
// fusionner les sous-ensembles résultants du tableau Q [] en p []
TopdownMerge (q, ibegin, imiddle, iend, p);
Les deux nouveaux appels récursifs ont été tapés au-dessus de l'appel récursif TopdownMerge (). Ces deux appels seront mémorisés avec TopdownMerge () et appelés autant de fois que nécessaire, chacun dans l'ordre inverse.
Si le tableau donné n'a pas d'élément, il ne devrait pas y avoir de tri. Si le nombre d'éléments dans le tableau donné est 1, alors le tableau est déjà trié, et aucun tri ne devrait avoir lieu. Ceci est pris en charge par une déclaration à l'intérieur mais en haut de la fonction codée extérieure, TopdownSplitMerge () comme suit:
void topdownSplitmerge (char q [], int ibegin, int iend, char p [])si (iend - ibegin<= 1)
retour;
int imiddle = (ibegin + iend) / 2;
TopdownSplitMerge (p, ibegin, imiddle, q);
TopdownSplitmerge (p, imiddle, iend, q);
TopdownMerge (q, ibegin, imiddle, iend, p);
La fonction précise pour fusionner et trier
Le nom de cette fonction est TopdownMerge (). Il est appelé récursivement par TopdownSplitMerge (). Le code est:
void topdownmerge (char p [], int ibegin, int imiddle, int iend, char q [])// Bien qu'il y ait des éléments dans les sous-ensembles gauche ou droit…
int i = ibegin;
int j = imiddle;
pour (int k = ibegin; k
Q [k] = p [i];
i = i + 1;
autre
Q [k] = p [j];
J = J + 1;
En théorie, cette fonction itère depuis le début de l'exécution de gauche (sous-ensemble) à la fin de l'exécution droite (sous-ensemble). Notez comment l'ambiguïté mentionnée ci-dessus a été prise en charge par la condition de la condition de l'IF-Construct.
Faire une copie unique pour tous les éléments
Au début du programme, après que la fonction ci-dessous (cette section), ait été appelée, tous les éléments du tableau donné doivent être copiés dans le tableau, q. Le code pour cela est:
void copyArray (char p [], int ibegin, int iend, char q [])pour (int i = ibegin; i
Il s'appelle une fois à partir de la fonction suivante. Cela prend comme arguments, le tableau donné, p, puis 0, puis n, et l'autre tableau Q, qui est en théorie vide mais qui a déjà le même nombre d'éléments que P. Iend, qui est le même que N, ici, est la longueur du tableau initialement donné.
Fonction pour lancer le programme
La fonction pour lancer le programme est:
void topdownMerGesort (char p [], char q [], int n)CopyArray (p, 0, n, q); // p [] est copié sur Q [] une fois
TopdownSplitMerge (Q, 0, N, P);
Il appelle la fonction CopyArray (), avec les arguments attendus. Il appelle ensuite la fonction principale, TopdownSplitMerge (), avec les positions des tableaux, P et Q, échangés. C'est pourquoi, dans le code topdownmerge (), les valeurs triées sont envoyées à Q et non à P.
Arrangement de code
Si les quatre fonctions codées ci-dessus sont tapées dans l'ordre suivant,
- void topdownmerge ()
- void topdownsplitmerge ()
- copyArray ()
- TopdownMerSort ()
alors le programme Mergesort (composé principalement de ces quatre fonctions) fonctionnera dans un compilateur C sans aucun problème.
C Fonction principale
Une fonction principale C appropriée pour ce programme est:
int main (int argc, char ** argv)char p [] = 'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p';
int sz = sizeof (p) / sizeof (p [0]);
char q [sz];
pour (int i = 0; i
TopdownMerSort (P, Q, SZ);
pour (int i = 0; i
printf ("\ n");
retour 0;
Conclusion
Diviser et conquérir l'algorithme divise le problème en pièces plus petites, avec l'espoir de les résoudre indépendamment. Une fois que toutes les petites pièces ont été résolues, leurs solutions sont combinées en une solution principale. Avec Merge-Sort, il y a une division continue de deux, jusqu'à ce que chaque sous-ensemble soit un élément de long, et automatiquement déjà trié. Rassembler ces courses à élément unique, implique des fonctions récursives et un tri réel, en commençant par des paires d'éléments uniques.