0

「アルゴリズムの紹介」で説明されているアルゴリズムを使用して Mergesort を実装しています。ただし、実行するたびに、ソートされた配列の最初の要素としてガベージ値を取得します。そのコードは次のとおりです。

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

void mergesort(int a[], int p, int r);

void merge(int a[], int p, int q, int r)
{
    int *left, *right;
    int i,j,k,l,n1,n2;
    n1 = q-p+1;
    n2 = r-q;
    left = malloc(sizeof(int)*(n1+1));
    right = malloc(sizeof(int)*(n2+1));
    for ( i = 0; i < n1; i++) {
        left[i] = a[p+i];
    }
    for ( j = 0; j < n2; j++) {
        right[j] = a[q+j+1];
    }
    left[n1] = INT_MAX;
    right[n2] = INT_MAX;
    i = 0;
    j = 0;
    for ( k = p; k <= r; k++) {
        if (left[i] <= right[j]) {
            a[k] = left[i];
            i++;
        }
        else {
            a[k] = right[j];
            j++;
        }
    }
    free(left);
    free(right);
    return ;
}

int main(int argc, char* argv[])
{
    int i;
    int a[] = {5,2,4,7,1,3,2,6} ;
    mergesort(a,0,sizeof(a)/sizeof(int));
    for ( i = 0; i < sizeof(a)/sizeof(int); i++) {
        printf("%d\n",a[i]);
    }
    return 0;
}

void mergesort(int a[], int p, int r)
{
    if (p < r) {
        int q;
        q = (p+r)/2 ;
        mergesort(a,p,q);
        mergesort(a,q+1,r);
        merge(a,p,q,r);
    }
}
4

3 に答える 3

2

マージソートパラメータの意味を明確に定義していないようです。ここで、最後の要素は配列の終わりを1つ過ぎたところに配置されています。

mergesort(a,0,sizeof(a)/sizeof(int));

しかし、ここで、

mergesort(a,p,q);
mergesort(a,q+1,r);

Qは配列の最後の要素を超えているようです。コードが最初のコードの後に​​続く場合、実際に値qをソートするのを忘れることになります。2番目の後に続く場合は、配列の終わりを1つ超えたガベージ値をソートしようとします。

于 2012-05-21T08:16:48.593 に答える
1

すべきではない

mergesort(a,0,sizeof(a)/sizeof(int));

なれ

 mergesort(a,0,sizeof(a)/sizeof(int)-1);

?

あなたがすることを考えると

 n1 = q-p+1;

等

ほぼ確実に、ここのどこかに off-by-one エラーがあります。

于 2012-05-21T08:03:33.647 に答える
0

含めるa[r]かどうかを選択する必要があります。ここであなたの選択は一貫していないため、エラーが発生します。

ここに良いコードがあります（私は含めませんa[r]）：

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

void mergesort(int a[], int p, int r);

void merge(int a[], int p, int q, int r)
{
    int *left, *right;
    int i,j,k,l,n1,n2;
    n1 = q-p;
    n2 = r-q;
    left = malloc(sizeof(int)*(n1+1));
    right = malloc(sizeof(int)*(n2+1));
    for ( i = 0; i < n1; i++) {
        left[i] = a[p+i];
    }
    for ( j = 0; j < n2; j++) {
        right[j] = a[q+j];
    }
    left[n1] = INT_MAX;
    right[n2] = INT_MAX;
    i = 0;
    j = 0;
    for ( k = p; k < r; k++) {
        if (left[i] <= right[j]) {
            a[k] = left[i];
            i++;
        }
        else {
            a[k] = right[j];
            j++;
        }
    }
    free(left);
    free(right);
    return ;
}

int main(int argc, char* argv[])
{
    int i;
    int a[] = {5,2,4,7,1,3,2,6} ;
    mergesort(a,0,sizeof(a)/sizeof(int));
    for ( i = 0; i < sizeof(a)/sizeof(int); i++) {
        printf("%d\n",a[i]);
    }
    return 0;
}

void mergesort(int a[], int p, int r)
{
    if (r-p > 1) {
        int q;
        q = (p+r)/2 ;
        mergesort(a,p,q);
        mergesort(a,q,r);
        merge(a,p,q,r);
    }
}
于 2012-05-21T08:01:02.623 に答える