このプログラムは 2 つの入力を受け取ります。最初の配列サイズ（n）と選択例：- nが100の場合、私のプログラムは100個の乱数を生成し、マージソートとクイックソートを使用してソートします。
ここでchoice==2と入力すると、両方のソートアルゴリズムにかかった時間が表示されます
私のプログラムは入力サイズ 10^8 まで動作しますが、10"10 まで動作させたいです。入力サイズ 10^9 を入力すると、セグメンテーション違反が発生します。割り当てに問題があり、入力サイズの場合、大量のメモリ .malloc が null を返します。 10^9 を超える
プログラムの入力サイズを改善する方法を教えてください。
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
long long merge(int *A,long long i,long long mid,long long j)
{
int *C;
C=(int *)malloc(sizeof(int)*(j-i+1));
long long r,start,k;
r=0;
start=i;
k=mid+1;
while((i<=mid)&&(k<=j))
{
if(A[i]>A[k])
{
C[r]=A[k];
r++;k++;
}
else
{
C[r]=A[i];
r++;i++;
}
}
while(i<=mid)
{
C[r]=A[i];
r++;i++;
}
while(k<=j)
{
C[r]=A[k];
r++;k++;
}
for(i=0;i<r;i++,start++)
A[start]=C[i];
free(C);
}
long long partition(int *A,long long i,long long j)
{
long long mid;
mid=(i+j)/2;
if(i<j)
{
partition(A,i,mid);
partition(A,mid+1,j);
merge(A,i,mid,j);
}
}
long long find_position(int A[],long long i,long long j)
{
long long pivot,temp,end;
end=j;
pivot=i;
while(i<j)
{
while(A[i]<=A[pivot]&&i<end)
i++;
while(A[j]>A[pivot])
j--;
if(i<j)
{
temp=A[i];
A[i]=A[j];
A[j]=temp;
}
}
temp=A[pivot];
A[pivot]=A[j];
A[j]=temp;
return j;
}
long long quicksort(int A[],long long i,long long j)
{
long long position;
if(j>i)
{
position = find_position(A,i,j);
quicksort(A,i,position-1);
quicksort(A,position+1,j);
}
}
int main()
{
clock_t start,end,quick_sort,merge_sort;
long long input_size,i;
int choice,x;
srand(time(NULL));
printf("Enter input Size\n");
scanf("%lld",&input_size);
int *A,*B;
printf("input your choice\n");
scanf("%d",&choice);
A=(int *)malloc(input_size*sizeof(int));
B=(int *)malloc(input_size*sizeof(int));
if(A==NULL||B==NULL)
{
printf("sorry that much memory can't be allocated\n");
return 0;
}
for(i=0;i<input_size;i++)
{
x=rand();
A[i]=x;
B[i]=x;
}
if(choice==1)
{
printf("Array entered by user\n");
for(i=0;i<input_size;i++)
printf("%d ",A[i]);
}
start=clock();
partition(A,0,input_size-1);
end=clock();
merge_sort=end-start;
if(choice==2)
printf("\n time taked by merge sort is %6.6f",((double)(merge_sort)/CLOCKS_PER_SEC));
if(choice==1)
{
printf("\nmerge sorted array\n");
for(i=0;i<input_size;i++)
printf("%d ",A[i]);
}
start=clock();
quicksort(B,0,input_size-1);
end=clock();
quick_sort=end-start;
if(choice==2)
printf("\n time taked by quick sort is %6.6f",((double)(quick_sort)/CLOCKS_PER_SEC));
if(choice==1)
{
printf("\nquick sorted array\n");
for(i=0;i<input_size;i++)
printf("%d ",B[i]);
}
printf("\n");
return 0;
}