0 
// msort.h
#ifndef _MSORT_H

void msort(int a[], int b[], int left, int right);

#endif //_MSORT_H


// msort.c
#include "msort.h"

void msort(int a[], int b[], int left, int right)
{
    if (left < right)
    {
        msort(a, b, left, (left + right) / 2);
        msort(a, b, (left + right) / 2 + 1, right);
        merge(a, b, left, right);
    }
}


// merge.h
#ifndef _MERGE_H_

void merge(int a[], int b[], int low, int high);

#endif //_MERGE_H_ 




// merge.c
#include <stdio.h>
#include "merge.h"

void merge(int a[], int b[], int low, int high)
{
    int mid, begin1, end1, begin2, end2, k;

    mid = (low + high) / 2;
    begin1 = low;
    end1 = mid;
    begin2 = mid + 1;
    end2 = high;
    k = 0;

    while (begin1 <= end1 && begin2 <= end2)
    {
        if (a[begin1] <= a[begin2])
            b[k++] = a[begin1++];
        else
            b[k++] = a[begin2++];
    }

    while (begin1 <= end1)
        b[k++] = a[begin1++];

    while (begin2 <= end2)
        b[k++] = a[begin2++];
}





// test_merge.c
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <malloc.h>
#include "msort.h"
#include "merge.h"

#define N 10

int main()
{
    int *a, *b, i, left, right;

    left = 0;
    right = N - 1;

    a = malloc(sizeof(int) * N);
    if (a == NULL)
        exit(0);
    b = malloc(sizeof(int) * N);
    if (b == NULL)
        exit(0);

    srand((unsigned)time(NULL));

    printf("array before sort:\n");
    for (i = 0; i < N; i++)
    {
        a[i] = rand() % 50;
        printf("%-5d", a[i]);
    }
    printf("\n");

    msort(a, b, left, right);

    printf("array after sort:\n");
    for (i = 0; i < N; i++)
    {
        printf("%-5d", b[i]);
    }
    printf("\n");

    free(a);
    free(b);
    return 0;

}

上記はマージソートコードです。配列が正しい順序になるまで msort.h および msort.c 再帰。merge.h と merge.c は、2 つの部分配列をマージします。test_merge.c はマージソートの単なるテストです。コンパイルおよびリンク時にエラーと警告は発生しません。しかし、出力が適切ではありません。理由が見つかりませんでした。

誰でも助けてもらえますか？

4

1 に答える 1

2

msortまたはの最初の配列を変更することはないため、 inmergeへの最後の呼び出しは、 への再帰呼び出しで行われたことを喜んで上書きします。mergemsortmsort

msort(a, b, left, right);

にmain等しい

merge(a, b, left, right);

ではmerge、マージされたチャンクをコピーして配列に戻す必要がありますa。その後、ソートされた配列が最後にa(および にもb) 含まれます。

void merge(int a[], int b[], int low, int high)
{
    int mid, begin1, end1, begin2, end2, k;

    mid = (low + high) / 2;
    begin1 = low;
    end1 = mid;
    begin2 = mid + 1;
    end2 = high;
    k = 0;

    while (begin1 <= end1 && begin2 <= end2)
    {
        if (a[begin1] <= a[begin2])
            b[k++] = a[begin1++];
        else
            b[k++] = a[begin2++];
    }

    while (begin1 <= end1)
        b[k++] = a[begin1++];

    while (begin2 <= end2)
        b[k++] = a[begin2++];
    /* Now copy back into a */
    for(begin1 = low, begin2 = 0; begin1 <= high; ++begin1, ++begin2) {
        a[begin1] = b[begin2];
    } 
}
于 2012-05-25T15:00:29.663 に答える