Mình mới viết một chuơng trình tính thời sắp xếp trên mảng các số nguyên tạo ngẫu nhiên bằng Mergesort đệ quy nhưng không chạy được.
Các bạn xem hộ mình với nhá. Mình nghĩ là hàm merge của mình có vấn đề
Code:
#include<stdio.h>
#include<conio.h>
#include<time.h>
#include<stdlib.h>
#include<time.h>
int *random(int n);
int swap(int *a,int i,int j);
int mergesort(int *a,int n);
void mergesort(int *a,int p,int r);
void merge(int *a,int p,int q,int r);
int main()
{
int i,n;
int *a;
printf("Nhap so phan tu:");
scanf("%d",&n);
a=random(n);
double timer;
time_t t1;
time_t t2;
time(&t1);
mergesort(a,0,n-1);
time(&t2);
timer=difftime(t2,t1);
printf("Running time = %lf\n",timer);
getch();
}
int *random(int n)
{
srand(time(NULL));
int *a;
int i;
a=(int *)malloc(n*sizeof(*a));
for(i=0;i<n;i++)
{
a[i]=rand();
if(a[i]==32767) a[i]=a[i]-1;
}
return a;
}
void mergesort(int *a,int p,int r)
{
int q;
if(p<r)
{
q=(p+r)/2;
mergesort(a,p,q);
mergesort(a,q+1,r);
merge(a,p,q,r);}
}
void merge(int *a,int p,int q,int r)
{
int *L1;
int *L2;
int i,j,k;
L1=(int *)malloc((q-p+2)*sizeof(*L1));
L1=(int *)malloc((r-q+1)*sizeof(*L2));
for(i=0;i<(q-p+1);i++)
L1[i]=a[p+i];
L1[i]=32767;
for(i=0;i<(r-q);i++)
L2[i]=a[q+i+1];
L2[i]=32767;
i=0;
j=0;
for(k=p;k<=r;k++)
{
if(L1[i]<=L2[j])
{
a[k]=L1[i];
i=i+1;
}
else
{
a[k]=L2[j];
j=j+1;
}
}
free(L1);
free(L2);
}