私はマージソート用のプログラムを書きました (基本的なアルゴリズムを書きました) - そしてそれはうまくいきます。ただし、非常に大きなファイルから整数を読み取る必要があるため、再帰呼び出しで配列を動的に宣言したいと考えていました。したがって、次のコードを書きましたが、いくつかのエラーが発生しています。どこで間違いを犯しているのかを特定するのを手伝ってもらえますか?
プログラムは、実際には配列内の反転の数をカウントすることです ( i < j および arr[i]>arr[j] の場合、これは反転です)。私が書いたプログラムは以下の通りです:
私が得るエラーは次のとおりです: std::bad_alloc at memory location 0x004dd940.. エラーメッセージが含まれるように質問を編集しました。実行が中断し、Visual Studio がデバッグ モードになり、ファイル osfinfo.c が開きます。
#include<stdio.h>
#include <iostream>
using namespace std;
unsigned int mixAndCount(int * arr,int low, int mid,int high) {
int *num = new int[high-low+1];// THIS IS WHERE THE ERROR OCCURS
int l = low ;
int r = mid+1;
unsigned int count=0;
int i =low;
while((l<=mid)&&(r<=high))
{
if(arr[l]<=arr[r])
{
num[i]=arr[l];
l++;
}
else
{
num[i]=arr[r];
r++;
count=count + (mid-l+1);
}
i++;
}
if(l>mid)
{
for(int k=r;k<=high;k++)
{
num[i]=arr[k];
i++;
}
}
else
{
for(int k=l;k<=mid;k++)
{
num[i]=arr[k];
i++;
}
}
for(int k=low;k<=high;k++) arr[k]=num[k];
delete[] num;
return count;
}
unsigned int mergeAndCount(int * arr, int low , int high ) {
if(low>=high) {
return 0;
}
else {
int mid = (low+high)/2;
unsigned int left = mergeAndCount(arr, low , mid);
unsigned right = mergeAndCount(arr, mid+1, high);
unsigned int split = mixAndCount(arr, low , mid , high);
return left+right+split;
}
}
int main ()
{
int numArr[100000];
FILE * input = fopen("IntegerArray.txt", "r");
int i =0;
while(!feof(input)) {
int num;
fscanf(input, "%d", &num);
numArr[i] = num;
i++;
}
fclose(input);
unsigned int count = mergeAndCount(numArr,0, i-1 );
cout<<count<<endl;
return 0;
}