Merge Sortierung gibt Müll Wert als Ausgabe

Question

Ich habe folgenden Code in c geschrieben, aber die Ausgabe des folgenden Programms ist immer ein Array von Müll Wert, meine alle eingegebenen Ganzzahlen werden irgendwo verloren, bitte helfen und sagen Sie mir, was und wo Fehler ist. danke :)

#include<stdio.h> 
#include<malloc.h> 

void merge(int a[],int beg,int mid,int end) 
{ 
    int n1=mid-beg+1; 
    int n2=end-mid; 
    int i=0,j=0,k=0; 

    int *p1 = (int*)malloc((n1)*sizeof(int)); 
    int *p2 = (int*)malloc((n2)*sizeof(int)); 

    for(i=0;i<n1;i++) 
     p1[i]=a[beg+i]; 

    for(j=0;j<n2;j++) 
     p2[j]=a[mid+1+j]; 
    i=j=0; 

    for(k=beg;k<=end;k++) 
    { 
     if(p1[i]<=p2[j]) 
     { 
      a[k]=p1[i]; 
      i=i+1; 
     } 
     else { 
      a[k]=p2[j]; 
      j=j+1; } 
    } 
} 
void merge_sort(int a[],int beg,int end) 
{ 
    if(beg<end) 
    { 
     int mid=(beg+end)/2; 

     merge_sort(a,beg,mid); 
     merge_sort(a,mid+1,end); 
     merge(a,beg,mid,end); 
    } 
} 
void main() 
{ 
    printf("Enter Array of size 10:\n"); 
    int a[10],i; 
    for(i=0;i<10;i++) 
     scanf("\n%d",&a[i]); 

    int n=sizeof a/sizeof a[0]; 

    merge_sort(a,0,n-1); 

    printf("\nSorted array is:\n"); 
    for(i=0;i<10;i++) 
     printf("%d\n",a[i]); 

} 

Answer 1

Sie haben nicht für den Zustand geprüft, wo man alle Elemente des Arrays im Ergebnis gesetzt werden, während einige Elemente in der zweiten Anordnung sind noch nicht an der richtigen Stelle.

nur für das Verständnis versuchen Sie merge Verfahren auf den folgenden Eingaben laufen -
a - {1,2,3,4,10,11,12,13,14}
beg - 0
end - 8
mid - 4

In Ihrer void merge(int a[],int beg,int mid,int end) Funktion die dritte for Schleife ersetzen mit -

for(k=beg;i<n1 && j<n2;k++) 
{ 
    if(p1[i]<=p2[j]) 
     a[k]=p1[i++]; 
    else 
     a[k]=p2[j++]; 
} 
while(i<n1) 
    a[k++] = p1[i++]; 
while(j<n2) 
    a[k++] = p2[j++]; 

Answer 2

Die Funktion der Zusammenführung ist falsch. Und Folgendes könnte funktionieren.

#include <stdio.h> 
#include <malloc.h> 

void merge(int a[],int beg,int mid,int end) 
{ 
    int n1=mid-beg+1; 
    int n2=end-mid; 
    int i=0,j=0,k=0; 

    int *p1 = (int*)malloc((n1)*sizeof(int)); 
    int *p2 = (int*)malloc((n2)*sizeof(int)); 

    for(i=0;i<n1;i++) 
     p1[i]=a[beg+i]; 

    for(j=0;j<n2;j++) 
     p2[j]=a[mid+1+j]; 
    i=j=0; 

    for(k=beg;k<=end;k++) 
    { 
     if (j >= n2 || (i < n1 && p1[i]<=p2[j])) 
     { 
      a[k]=p1[i]; 
      i=i+1; 
     } 
     else 
     { 
      a[k]=p2[j]; 
      j=j+1; 
     } 
    } 
} 

void merge_sort(int a[],int beg,int end) 
{ 
    if(beg<end) 
    { 
     int mid=(beg+end)/2; 

     merge_sort(a,beg,mid); 
     merge_sort(a,mid+1,end); 
     merge(a,beg,mid,end); 
    } 
} 

int main() 
{ 
    printf("Enter Array of size 10:\n"); 
    int a[10],i; 
    for(i=0;i<10;i++) 
     scanf("\n%d",&a[i]); 

    int n = sizeof a/sizeof a[0]; 

    merge_sort(a,0,n-1); 

    printf("\nSorted array is:\n"); 
    for(i=0;i<10;i++) 
     printf("%d\n",a[i]); 

    return 0; 
}