Merge Sort Programm

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; 
} 

Dies ist ein Merge-Sortierprogramm. Warum gibt es Laufzeitfehler, wenn jemand erklären kann? Es gibt keinen Fehler in diesem Programm

Ich habe dies 10 mal versucht. Und nicht in der Lage, die Lösung zu finden.

Answer 1

Wenn Sie mergesort(a, 3, 5) rufen geschieht Folgendes:

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 

Mit anderen Worten: Eine Endlosschleife.

Vielleicht möchten Sie diese stattdessen:

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

     ^ ^
     notice 

So wie habe ich den Fehler finden?

Sehr einfach - verwenden Sie einfach einige printf-debug.

Zuerst habe ich einen Druck in Beginn mergesort - wie:

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); 
    } 
} 

und bekam die Ausgabe:

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

, die mir gesagt, dass es eine Endlosschleife für die Eingabe war Werte 3 und 5.

Dann habe ich einen Druck von m

und bekam die Ausgabe:

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

so offensichtlich m wurde falsch berechnet.

Blick nah an

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

ist wurde klar, dass die Zugabe vor die Teilung sein sollte. Ein Satz von (....) fehlte.

Ich hoffe, Sie können dieses Debug-Beispiel für Ihr eigenes Debuggen verwenden.