1

次のコードは、マージソートを行うことになっている CLRS ( Corman, Leiserson, Rivest, Stein — 'Introduction to Algorithms' ) の教科書に従っています。

関数で何か問題が発生していることはわかっていますが、発生しているエラーを特定することはできませんmergesort()。機能的には問題ないと思いますmerge()。

/* Merge sort as per CLRS */
#include <stdio.h>
#include <stdlib.h>

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

void mergeSort(int* a,int p,int r){
if( p < r){

    int q = ( p + r ) / 2;
    mergeSort(a,p,q);
    mergeSort(a,p+1,r);
    merge(a,p,q,r);
}

else return;

}

int main(int argc, char* argv[]){
int a[] = {9,21,4,15,1,3};

mergeSort(a,0,5);

int i;
for( i = 0 ; i < 6 ; i++){
    printf("%d ",a[i]);
}
return 0;

}
4

2 に答える 2

4 
void merge(int *a,int p,int q,int r){
    int n1 = q - p + 1;
    int n2 = r - q;
    int* l = malloc((n1+1)*sizeof(int));
    int* ri = malloc((n2+1)*sizeof(int));
    int i,j;
    for(i = 0 ; i < n1 ; i++)
        l[i] = a[p+i-1];
    for(i = 0 ; i < n2 ; i++)
        ri[i] = a[q+i];

p-1indexから indexq-1までlの要素と、 indexqからr-1までの要素を書き込んでいますri。の場合p == 0、範囲外にアクセスします。

ただし、要素を index から まで並べ替えたいとしpますr。

void merge(int *a,int p,int q,int r){
    int n1 = q - p + 1;
    int n2 = r - q;
    int* l = malloc((n1)*sizeof(int));
    int* ri = malloc((n2)*sizeof(int));
    int i,j;
    for(i = 0 ; i < n1 ; i++)
        l[i] = a[p+i];
    for(i = 0 ; i < n2 ; i++)
        ri[i] = a[q+i+1];

また、両方のインデックスが対応する終了インデックスrespより小さいかどうかを確認する必要がiあります。、そしてその部分の終わりに達したら、残りを他の部分から配列にコピーします。配列に大きなエントリが含まれている場合、ガード値はひどく失敗します。jn1n2

while(i < n1 && j < n2) {
    if (ri[j] < l[i]) {
        a[k++] = ri[j++];
    } else {
        a[k++] = l[i++];
    }
}
while(i < n1) {
    a[k++] = l[i++];
}
while(j < n2) {
    a[k++] = ri[j++];
}
于 2013-01-09T17:49:57.937 に答える
3

mergeSort()コードには、次のものがあります。

int q = ( p + r ) / 2;
mergeSort(a,p,q);
mergeSort(a,p+1,r);
merge(a,p,q,r);

mergeSort2番目は であるべきだと思いますmergeSort(a, q+1, r);よね？

これは、 Daniel Fischerによる分析とは別のものであり、独立しています。

ではmerge()、2 つの配列を割り当てます。これらの配列は解放しません。これはメモリ リークです。また、割り当てが成功したことも確認する必要があります。

于 2013-01-09T17:52:36.333 に答える