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.

InformationsquelleAutor James Dean | 2013-07-04

Schreibe einen Kommentar