La compréhension de la Récursivité de mergesort
La plupart des mergesort implémentations je vois sont similaires à ce. introduction aux algorithmes livre avec en ligne implantations je recherche. Mon récursivité côtelettes de ne pas aller beaucoup plus loin que de jouer avec de Fibonacci génération (qui a été assez simple) donc c'est peut-être le plusieurs récurrences souffler mon esprit, mais je ne peux même pas parcourir le code, et comprendre ce qui se passe avant même que j'ai même frappé la fonction de fusion.
Comment est-il pas à pas dans cette? Est-il une stratégie ou de lecture que je devais subir de mieux comprendre le processus ici?
void mergesort(int *a, int*b, int low, int high)
{
int pivot;
if(low<high)
{
pivot=(low+high)/2;
mergesort(a,b,low,pivot);
mergesort(a,b,pivot+1,high);
merge(a,b,low,pivot,high);
}
}
et de la fusion(bien franchement, je suis mentalement bloqué avant même d'arriver à cette partie)
void merge(int *a, int *b, int low, int pivot, int high)
{
int h,i,j,k;
h=low;
i=low;
j=pivot+1;
while((h<=pivot)&&(j<=high))
{
if(a[h]<=a[j])
{
b[i]=a[h];
h++;
}
else
{
b[i]=a[j];
j++;
}
i++;
}
if(h>pivot)
{
for(k=j; k<=high; k++)
{
b[i]=a[k];
i++;
}
}
else
{
for(k=h; k<=pivot; k++)
{
b[i]=a[k];
i++;
}
}
for(k=low; k<=high; k++) a[k]=b[k];
}
Vous devez vous connecter pour publier un commentaire.
Je pense que le "tri" le nom de la fonction MergeSort est un peu un abus de langage, il faut vraiment être appelé "diviser".
Ici est une visualisation de l'algorithme dans le processus.
Chaque fois que la fonction se répète, c'est de travailler sur une plus petite et la plus petite subdivision de l'entrée de tableau, en commençant par la gauche que la moitié. Chaque fois que la fonction renvoie de la récursivité, il continuera sur et commencer à travailler soit sur la moitié droite, ou de répéter de nouveau et de travailler sur une plus grande moitié.
Comme ce
DE FUSION TRI:
1) Diviser le tableau en deux
2) Trier la moitié gauche
3) Trier la moitié droite
4) Fusionner les deux moitiés ensemble
Une chose évidente à faire serait d'essayer cette fusion tri sur un petit tableau, dire la taille 8 (puissance de 2 est pratique ici), sur le papier. Imaginez que vous êtes un ordinateur d'exécuter le code, et de voir si il commence à devenir un peu plus clair.
Votre question est un peu ambigu, car vous n'expliquez pas ce que vous trouvez à confusion, mais il semble que vous essayez de dérouler les appels récursifs dans votre tête. Qui peut ou peut ne pas être une bonne chose, mais je pense qu'il peut facilement conduire à avoir trop dans votre tête à la fois. Au lieu d'essayer de retracer le code du début à la fin, voir si vous pouvez comprendre la notion abstraite. Fusion de tri:
(1) devrait être assez évident et intuitif pour vous. Pour l'étape (2) l'idée clé est présent, la moitié gauche d'un tableau... est un tableau. En supposant que votre fusion tri fonctionne, il devrait être en mesure de trier la moitié gauche du tableau. Droit? L'étape (4) est en fait une jolie partie intuitive de l'algorithme. Un exemple devrait la rendre insignifiante:
Donc en supposant que vous comprenez (1) et (4), une autre façon de penser de la sorte de fusion ne serait-ce. Imaginez quelqu'un d'autre a écrit
mergesort()et vous êtes sûr qu'il fonctionne. Ensuite, vous pouvez utiliser que la mise en œuvre demergesort()à écrire:Noter que
sortne pas utiliser la récursivité. Il dit seulement "trier les deux moitiés, et puis les fusionner". Si vous avez compris l'exemple de fusion ci-dessus, alors vous avez la chance de voir intuitivement que cesortfonction semble faire ce qu'il dit... en quelque sorte.Maintenant, si vous regardez plus attentivement...
sort()ressemble à peu près exactement commemergesort()! C'est parce que c'estmergesort()(sauf qu'il n'ont pas la base de cas parce qu'elle n'est pas récursif!).Mais c'est la façon dont j'aime la pensée de fonctions récursives--supposons que la fonction fonctionne, quand vous l'appelez. La traiter comme une boîte noire qui fait ce que vous en avez besoin. Lorsque vous effectuez cette hypothèse, à comprendre comment remplir cette boîte noire est souvent facile. Pour une entrée donnée, vous pouvez le décomposer en petites entrées pour nourrir votre boîte noire? Après à vous de résoudre ce problème, la seule chose qui reste est de la manipulation de la base de cas au début de votre fonction (qui sont les cas où vous n'avez pas besoin de faire des appels récursifs. Par exemple,
mergesort([])retourne un tableau vide; il n'est pas un appel récursif demergesort()).Enfin, c'est un peu abstrait, mais une bonne façon de comprendre la récursivité est fait pour écrire des preuves mathématiques à l'aide de l'induction. La même stratégie utilisée pour écrire une preuve par induction est utilisé pour écrire une fonction récursive:
Mathématiques la preuve:
nnFonction récursive:
nnConcernant la récursivité le cadre de la fusion de tri, j'ai trouvé ce page être très très utile. Vous pouvez suivre le code tel qu'il est exécuté. Il vous montre ce qui est exécuté en premier, et ce qui suit.
Tom
la
mergesort()simplement divise le tableau en deux moitiés jusqu'à ce que leifcondition échoue c'estlow < high. Comme vous l'appelezmergesort()deux fois : l'une aveclowàpivotet la deuxième avecpivot+1àhigh, cela permettra de diviser les sous-matrices de même plus encore.Prenons un exemple :
Il répétera jusqu'à ce que vous avez au moins 1 élément dans chaque
leftainsi querighttableau.En fin de compte, vous aurez quelque chose de similaire à ceci :
Voir la fusion des étapes dans la réponse donnée par @roliu
Mes excuses si cela a été répondu de cette façon. Je reconnais que ce n'est qu'une esquisse, plutôt que d'une profonde explication.
Alors qu'il n'est pas évident de voir comment le code des cartes de la récursivité, j'ai été capable de comprendre la récursivité dans un sens général de cette façon.
Prendre l'exemple des ménagères de définir
{2,9,7,5}comme entrée. Le merge_sort algorithme est désigné par "ms" pour des raisons de concision ci-dessous. Ensuite, nous pouvons esquisser l'opération:Il est important de noter que merge_sort d'un singulet (comme
{2}) est tout simplement le singulet (ms(2) ={2}), de sorte que, au niveau le plus profond de la récursivité nous obtenir notre première réponse. Le reste des réponses ensuite culbuter comme des dominos que l'intérieur récurrences de finition et sont fusionnés.Une partie du génie de l'algorithme est la façon dont il construit la formule récursive de l'étape 1 est automatiquement grâce à sa construction. Ce qui m'a aidé a l'exercice de la pensée comment faire pour activer l'étape 1 ci-dessus à partir d'une statique de la formule générale de la récursivité.
processus de diviser le problème en sous-problèmes
Exemple, vous aidera à comprendre la récursivité. int A[]={numéro de l'élément à être court-circuité.}, int p=0; (amant de l'indice). int r= A. length - 1;(Supérieur indice).
Je sais que c'est une vieille question, mais je voulais lancer ma pensée de ce qui m'a aidé à comprendre fusion de tri.
Il y a deux grandes parties à la fusion et le tri
Le rôle de la recurison est tout simplement la division de la partie.
Je pense que ce qui confond la plupart des gens, c'est qu'ils pensent qu'il ya beaucoup de logique dans la séparation et la détermination de ce split, mais la plupart de la logique réelle de tri qui se passe sur le de fusion. La récursivité est simplement là pour diviser et de faire la première moitié et la seconde moitié est vraiment juste la boucle, la copie de choses.
Je vois certaines réponses qui mentionnent des pivots mais je recommanderais de ne pas associer le mot "pivot" avec la fusion et le tri parce que c'est un moyen facile de confondre la fusion de tri avec quicksort (qui repose fortement sur le choix d'un "pivot"). Ils sont tous les deux de "diviser et conquérir" les algorithmes. Pour la fusion et le tri de la division est toujours le cas dans le milieu alors que pour quicksort vous pouvez être à l'aise avec la division lors du choix optimal de pivot.
Lorsque vous appelez la méthode récursive il n'exécute pas la fonction réelle dans le même temps, il est pile dans la pile mémoire. Et lorsque la condition n'est pas satisfaite alors il va à la ligne suivante.
Considérer que c'est votre tableau:
De sorte que votre méthode de fusion de tri fonctionnera comme ci-dessous:
De sorte que tous tri des valeurs de stocker dans le vide arr.
Il pourrait aider à comprendre le comment fonction récursive œuvres