Teile und herrsche-Paradigma und Rekursion in C - Merge-sort Beispiel
Ich kann nicht verstehen, wie Teile und herrsche-algorithmen implementiert werden, die in C.
Damit meine ich, dass ich verstehe, der Algorithmus aber nicht zu verstehen, warum und wie es funktioniert, wenn in C geschrieben.
Welche Anweisungen ausgeführt werden und was bestimmt die Reihenfolge Ihrer Ausführung im folgenden Beispiel?
In anderen Worten, warum "merge_sort Initialisierung", "merge_sort erste", "merge_sort zweite" und "Zusammenführen" angezeigt werden, wie Sie es tun?
#include<stdio.h>
int arr[8]={1, 2, 3, 4, 5, 6, 7, 8};
int main()
{
int i;
merge_sort(arr, 0, 7);
printf("Sorted array:");
for(i = 0; i < 8; i++)
printf("%d", arr[i]);
return 0;
}
int merge_sort(int arr[],int low,int high)
{
printf("\nmerge_sort initialization\n");
int mid;
if(low < high)
{
mid = (low + high) / 2;
//Divide and Conquer
merge_sort(arr, low, mid);
printf("\n merge_sort first\n");
merge_sort(arr, mid + 1, high);
printf("\n merge_sort second\n");
//Combine
merge(arr, low, mid, high);
printf("\nmerging\n");
}
return 0;
}
int merge(int arr[], int l, int m, int h)
{
int arr1[10], arr2[10];
int n1, n2, i, j, k;
n1 = m - l + 1;
n2 = h - m;
for(i = 0; i < n1; i++)
arr1[i] = arr[l + i];
for(j = 0; j < n2; j++)
arr2[j] = arr[m + j + 1];
arr1[i] = 9999;
arr2[j] = 9999;
i = 0;
j = 0;
for(k = l; k <= h; k++)
{
if(arr1[i] <= arr2[j])
arr[k] = arr1[i++];
else
arr[k] = arr2[j++];
}
return 0;
}
Vielen Dank im Voraus für Eure Antworten.
Erster Gedankenstrich Ihrem code
Es ist eingerückt.
Nicht in lesbarer Weise.
Danke für den edit.
gehen Sie dann durch ein kleines Beispiel mit Stift und Papier, und beobachten Sie, in welcher Reihenfolge Sie deuten der Drucke. Rekursion ist eine Sache, die Sie nur verstehen, indem man es tut. Ich glaube nicht, dass irgendjemand hier helfen kann, dass Sie mit.
Es ist eingerückt.
Nicht in lesbarer Weise.
Danke für den edit.
gehen Sie dann durch ein kleines Beispiel mit Stift und Papier, und beobachten Sie, in welcher Reihenfolge Sie deuten der Drucke. Rekursion ist eine Sache, die Sie nur verstehen, indem man es tut. Ich glaube nicht, dass irgendjemand hier helfen kann, dass Sie mit.
InformationsquelleAutor James Dean | 2013-07-04
Du musst angemeldet sein, um einen Kommentar abzugeben.
Ich bin nicht sicher, warum Sie sind, Leute zu Fragen, damit Sie verstehen den Algorithmus. Kann ich nur unterstützen Sie, aber Sie haben, um durch Sie gehen.
Zusammenführen, kurz Sie haben zu schneiden Sie das array in zwei Teile. angenommen, Sie haben 10 Elemente dann
high=0
undlow=10-1=1
.mid = (9+0)/2 = 4
. Also, Sie haben unterteilt, dem main-array auf 2 Teile vom 1. element bis 5. und vom 6. element 10 (1..10). Wenn Sie jemals haben mehr als ein element in einem Stück, das Sie schneiden Sie es in zwei wieder. Am Ende Zusammenführen, D. H. hinzufügen von arrays wieder, aber in aufsteigender Reihenfolge. Endlich bekommen Sie ein einzelnes array sortiert. Seine sehr schwer zu erklären, jedes Stück. Ich denke, dieser link von wiki helfen kann. http://en.wikipedia.org/wiki/Merge_sortKommt jetzt die Funktion aufrufen. main-Funktion ruft
merge_sort
es übergeben wird, low und hight (die vollständige Palette von array), aber innerhalb dieser Funktion diemerge_sort
aufgerufen werden, indem er sich zweimal mit der ersten Hälfte Palette (ab zur Mitte Weg, und nach midway und letzten element). Jeder Anruf wird wieder das gleiche tun (teilen Sie das array, und rufen Sie mit der ersten Hälfte und die Hälfte senden). Dieser Prozess wird weiter gehen.merge
Funktion wird das array in sortierter Art und Weise. Das ist alles, was Sie brauchen. Wenn Sie nicht klar ausdrucken, oder Debuggen Sie die Wert von Parameter.InformationsquelleAutor pcbabu