mergesort Cの実装

Question

私はこのコードをmergesortのアルゴリズムに従ってXcodeのC言語で書いています。 問題は、時々私はEXC_BAD_ACCESSを取得し、私はどこでエラーを管理することができないということです！ マージアルゴリズムが動作するはずです（私はマージソート関数外で試してみました！）。あなたの助けと忍耐ありがとう！

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 
#define DIM 6 

void mymerge (int v[], int i1,int i2, int last); //mergesort core: merge two ordinated arrays in one bigger ordinated array 
void mymergesort (int v[], int lower, int upper);//mergesort 
void printv (int v[],int lower, int upper); 

int main() { 
    int i; 
    srand((unsigned int)time(NULL)); 
    int v[DIM]; 
    for (i=0; i<DIM; i++) 
     v[i]=rand()%15; 
    printv(v, 0, DIM-1); 
    getc(stdin); 
    mymergesort(v, 0, DIM-1); 
    printv(v, 0, DIM-1); 
} 
void printv (int v[],int lower, int upper){ 
    int i; 
    for (i=lower; i<=upper; i++) 
    printf("%d\t",v[i]); 
} 
void mymergesort (int v[], int lower, int upper){ 
    int mid=(upper+lower)/2; 
    if (upper<lower) { 
     mymergesort(v, lower, mid); 
     mymergesort(v, mid+1, upper); 
     mymerge(v,lower,mid+1,upper); 
    } 
} 
void mymerge (int v[], int i1,int i2, int last){ 
    int i=i1,j=i2,k=i1,*vout; 
    vout=(int*)malloc((last-i1+1)*sizeof(int)); 
    while (i<i2 && j<=last) { 
     if (v[i]<=v[j]) { 
      vout[k++]=v[i++]; 
     }else { 
      vout[k++]=v[j++]; 
     } 
    } 
    for (;i<i2;i++) vout[k++]=v[i]; 
    for (;j<=last;j++) vout[k++]=v[j]; 
    for (k=i1; k<=last; k++) v[k]=vout[k]; 
free(vout); 
} 

編集： ありがとうございます！私は大きな配列（200要素）をソートしようとすると別の問題があると思うと思いますが、プログラムは動作しません（解放されたオブジェクトのチェックサムが解放された可能性があります）。しかし、xCodeデバッガから実行すると、すべて正常に動作します。

Answer 1

これは、vout=(int*)malloc((last-i1)*sizeof(int));が間違っています。

最初に、希望する要素の数はlast-i1+1で、last-i1ではなく、古典的なものが1つあります。この種のエラーは、Cコードの規約が、下限と上限を排他的にすることの理由の1つです。+1と-1の場合は、スクラップする機会が少なくなります。

さらに深刻なエラーは、voutから開始して、i1から始まることです。このようにすれば、last+1要素をvoutに割り当てる必要があり、最初のi1（インデックス0 .. i1-1）は使用しないでください。

修正：まず、last-i1+1要素を割り当てます。次に、最初にkを0に初期化し、i1ではなく初期化します。最後に、最終コピーを

for (k=i1; k<=last; k++) v[k] = vout[k-i1]; 

Answer 2

に変更してください。 1つは、中点の計算が正しくないことです。(upper - lower)/ 2を使用しますが、これはlowerとupperの間にあるとは限りません。あなたが実際にしたいのはlower + (upper - lower)/2です。これは、ソートする区間で唯一の1の数があるかどうどんな仕事をする必要もありません - そうmymergesort()関数は次のようになります。

void mymergesort (int v[], int lower, int upper) 
{ 
    if (upper > lower) { 
     int mid = lower + (upper - lower)/2; 

     mymergesort(v, lower, mid); 
     mymergesort(v, mid+1, upper); 
     mymerge(v,lower,mid+1,upper); 
    } 
} 

第二の問題はmymerge()機能が一つですでにFabian Giesenが指摘。

Answer 3

#include<stdio.h> 
#include<conio.h> 
#define max 20 
/*** function for merging the adjecent subarrays in sorted order ***/ 
void merge(int A[max],int n,int low,int high, int mid) 
{ 
    int i=low,j=mid+1,k,temp; 
    while((i<=j)&&(j<=high))  
    { 
     if(A[i]>A[j])   /** if element of the second half is greater then exchg and shift **/ 
     { 
      temp=A[j]; 
      for(k=j;k>i;k--) /** shifting the elements **/ 
      { 
      A[k]=A[k-1]; 
      } 
      A[i]=temp; 
      j++; 
     } 
     i++; 
    } 
} 
/******* iterative function for merge sort ********/ 
void merge_sort(int A[max],int n,int low,int high) 
{ 
    int mid; 
    if(low<high)      /** terminating condition **/ 
    { 
     mid=(high+low)/2;   /** calculating the mid point ***/ 
     merge_sort(A,n,low,mid);  /*** recursive call for left half of the array ***/ 
     merge_sort(A,n,mid+1,high); /*** recursive call for right half of the array ***/ 
     merge(A,n,low,high,mid); /** merging the both parts of the array **/ 
    } 
} 
/******* begening of the main function **********/ 
int main() 
{ 
    int A[max],n,i; 
    /** reading the inputs fro users **/ 
    printf("\n enter the size of the array\n"); 
    scanf("%d",&n); 
    printf("\n enter the array \n"); 
    for(i=0;i<n;i++) 
    { 
     scanf("%d",&A[i]);     
    } 
    /*** calling merge sort ***/ 
    merge_sort(A,n,0,n-1); 
    /** printing the sorted array **/ 
    for(i=0;i<10;i++) 
    { 
     printf("\n\t%d",A[i]);     
    } 
    getch(); 
    return 0; 
} 

Answer 4

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

void merge(int *a, int n1, int *b, int n2, int *arr) 
{ 
    int i=0, j=0, n=0; 
    while(i<n1 && j<n2) 
    { 
    if (a[i] < b[j]) 
    { 
     arr[n++] = a[i]; 
     i++; 
    } 
    else 
    { 
     arr[n++] = b[j]; 
     j++; 
    } 
    } 
    while(i < n1) 
    arr[n++] = a[i++]; 
    while(j < n2) 
    arr[n++] = b[j++]; 
} 
void merge_sort(int *a, int n) 
{ 
    int left[n/2], right[n-n/2],i=0; 
    if (n<=1) 
    return ; 
    while(i<n/2) 
    left[i] = a[i++]; 
    while(i<n) 
    right[i - n/2] = a[i++]; 
    merge_sort(left, n/2); 
    merge_sort(right, n-n/2); 
    merge(left, n/2, right, n-n/2, a); 
} 
void main() 
{ 
    int a[] = { 6, 5, 3, 1,9, 8, 7, 2, 4},i; 
    merge_sort(a,sizeof(a)/sizeof(a[0])); 
    for(i=0;i<9;i++) 
    printf("--%d",a[i]); 
    printf("\n"); 
} 


-- s.k