MergeSortの再帰

Question

私のコードを編集して、明白な間違いを削除しました。私はまだ私のmergesplit関数が再帰的でない理由を見つけることができません。一度だけ実行されます。いくつかの人が私に詳細な解決策を教えてください。

#include<bits/stdc++.h> 

void Merge_Sort(int a[],int p,int q,int mid); 

void Merge_Split(int a[],int p,int q)//recursive function 
{ 
int mid; 
if (p<q) 
{ 
    mid=(p+q)/2; 
    Merge_Split(a,p,mid); 
    Merge_Split(a,mid+1,q); 
    Merge_Sort(a,p,q,mid); 
} 
return; 
} 

void Merge_Sort(int a[], int p,int q,int mid)//sorting function 
{ 
int b[50]; 
int i,j,x; 
for(i=p,j=mid+1,x=p;i<=mid,j<q;) 
{ 
    if(a[j]<=a[i]) 
    b[x++]=a[j++]; 
    else 
    b[x++]=a[i++]; 
} 
while(i<=mid) 
{ 
    b[x++]=a[i++]; 
} 
while(j<=q) 
{ 
    b[x++]=a[j++]; 
} 
for(int i=p;i<q;i++) 
    a[i]=b[i]; 
} 

int main() 
{ 
int a[5],x=0,n=5; 
for(int i=0;i<n;i++) 
    scanf("%d", &a[i]); 
Merge_Split(a,0,5); 
for(int i=0;i<5;i++) 
    printf("%d", a[i]); 
return 0; 
} 

このコードは正常に動作するはずです。私は自分の問題を見つけることができません。親切に助けてください。

Answer 1

あなたは開いた/閉じた間隔でうんざりしていました。あなたのインターバルのタイプを決めたら、あなたのコードとあなたの規約とを一致させます。

Merge_Split(a,0,5)は、左閉じ、右開きの間隔を使用することを示します。これらの変化に

for(i=p,j=mid,x=p;i<mid,j<q;)

while(i<mid)

フルコード：

if (p<q)

Merge_Split(a,p,mid); 
Merge_Split(a,mid,q); 
Merge_Sort(a,p,q,mid); 

そして：その場合

#include<bits/stdc++.h> 

void Merge_Sort(int a[],int p,int q,int mid); 

void Merge_Split(int a[],int p,int q)//recursive function 
{ 
int mid; 
if (p<q - 1) 
{ 
    mid=(p+q)/2; 
    Merge_Split(a,p,mid); 
    Merge_Split(a,mid,q); 
    Merge_Sort(a,p,q,mid); 
} 
return; 
} 

void Merge_Sort(int a[], int p,int q,int mid)//sorting function 
{ 
int b[50]; 
int i,j,x; 
for(i=p,j=mid,x=p;i<mid,j<q;) 
{ 
    if(a[j]<=a[i]) 
    b[x++]=a[j++]; 
    else 
    b[x++]=a[i++]; 
} 
while(i<mid) 
{ 
    b[x++]=a[i++]; 
} 
while(j<q) 
{ 
    b[x++]=a[j++]; 
} 
for(int i=p;i<q;i++) 
    a[i]=b[i]; 
} 

int main() 
{ 
int a[5],x=0,n=5; 
for(int i=0;i<n;i++) 
    scanf("%d", &a[i]); 
Merge_Split(a,0,5); 
for(int i=0;i<5;i++) 
    printf("%d", a[i]); 
return 0; 
}