マージソートプログラム

Question

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

void merge(int a[],int l,int m,int r) 
{ 
    int i,j,k; 
    int n1= m - l + 1; 
    int n2= r - m; 
    int L[n1],R[n2]; 
    for(i=0;i<n1;i++) 
     L[i]=a[l+i]; 
    for(j=0;j<n2;j++) 
     R[j]=a[m + 1+ j]; 
    i=0;j=0;k=l; 
    while(i<n1 && j<n2) 
    { 
     if(L[i]<R[j]) 
     { 
      a[k]=L[i]; 
      i++; 
     } 
     else 
     { 
      a[k]=R[j]; 
      j++; 
     } 
     k++; 
    } 
    while(i<n1) 
    { 
     a[k]=L[i]; 
     i++; 
     k++; 
    } 
    while(j<n2) 
    { 
     a[k]=R[j]; 
     j++; 
     k++; 
    } 
} 

void mergeSort(int a[],int l,int r) 
{ 
    if(l<r) 
    { 
     int m = l+(r-1)/2; 
     mergeSort(a,l,m); 
     mergeSort(a,m+1,r); 
     merge(a,l,m,r); 
    } 
} 

void printArray(int a[],int n) 
{ 
    int i; 
    for(i=0;i<n;i++) 
     printf("%d ",a[i]); 
    printf("\n"); 
} 

int main() 
{ 
    int a[]= { 
       12,76,34,45,63,98 
      }; 
    int n = sizeof(a)/sizeof(a[0]); 
    printf("The element entered in array "); 
    printArray(a,n); 
    mergeSort(a,0,n-1); 
    printf("The element after sorting "); 
    printArray(a,n); 
    return 0; 
} 

これはマージソートプログラムです。なぜ誰かが説明できればランタイムエラーを起こすのですか？このプログラムにエラーはありません

私はこれを10回試しました。そして解決策を見つけることができません。あなたがmergesort(a, 3, 5)を呼び出すと

Answer 1

次の処理が行われます。つまり

int m = l+(r-1)/2; // 3 + (5-1)/2 -> 3 + 4/2 -> 3 + 2 -> 5 
mergeSort(a,l,m); // So this will call: mergesort(a, 3, 5) again 

：無限ループを。

たぶんあなたの代わりにこれをしたい：

int m = (l+(r-1))/2; 

     ^ ^
     notice 

それでは、どのように私は、バグを見つけましたか？

非常に簡単です - いくつかのprintf-debugを使用してください。

まず私はmergesortの開始で印刷を追加 - のような：

void mergeSort(int a[],int l,int r) 
{ 
    printf("mergesort %d %d\n", l, r); // Debug print 
    if(l<r) 
    { 
     int m = (l+(r-1))/2; 
     mergeSort(a,l,m); 
     mergeSort(a,m+1,r); 
     merge(a,l,m,r); 
    } 
} 

を出力ました：

mergesort 3 5 
mergesort 3 5 
mergesort 3 5 
... 
... 

入力は3値のための無限ループがあったと教えてくれましたし、 5.

は、その後、私はm

の印刷を追加しました

と出力ました：

mergesort 3 5 
m 5 
mergesort 3 5 
m 5 
mergesort 3 5 
m 5 

ので、明らかにmが誤って計算したが。

int m = l+(r-1)/2; 

に近い見て

は

さらには分割前でなければならないことが明らかにされました。 (....)のセットがありませんでした。

ご希望のデバッグサンプルを自分のデバッグ用に使用できますか？