-1

このマージソート アルゴリズムを再帰呼び出しで作成しようとしているときに、std::out_of_range の例外が発生しました。

デバッグやエラーの原因究明についてはよくわかりません。以下に、コード（完全ではなく、一部のみ）と同じコードを含むソースファイル（もちろん完全版）を投稿します。

提案がこのエラーに対して何の助けにもならない場合でも、喜んで耳を傾けますので、お気軽にこのコードにコメントして、私を冗談にしてください :)

https://docs.google.com/file/d/0ByVN9ccAyFY2dkVLN0ZlTWVHZG8/edit

主な機能

int main()
{
vector<int> original;   //input vector
input (&original);      //write input to vector<int> original

divide(&original);      //pass the vector

for(unsigned int i=0;i<original.size();i++)//output the results
cout<<original.at(i);
}

入力機能

    int input(vector<int> *inVec) //read all input until non-integer
{
int tmp;
while (cin>>tmp)
inVec->push_back(tmp);
for(unsigned int i=0;i<inVec->size();i++)
cout<<inVec->at(i)<<endl;
}

分ける

int divide(vector<int> *original)
{
int origL=original->size();
if(origL>1)
{
vector<int> first;      //vectors for holding 2 halfs of "original"
vector<int> second;     //

first.assign(original->begin(),original->begin()+origL/2);//1st half of "original"
second.assign(original->begin()+origL/2+1,original->end());//2nd half

divide(&first);     //recursive call until "first" and
divide(&second);    //"second" include only one number

merge(&first,&second,original);//merge first and second back into one vector
}
}

マージ機能

int merge(vector<int> *A,vector<int> *B,vector<int> *original)
{
//clear the original vector. we will use it to store sorted results.
original->erase(original->begin(),original->end());
unsigned int i=0,j=0;                                   

//out the smallest number from A and B into
//original[0] and so on. This makes it a 
//sorting algorithm.
for(i=0;i<A->size();i++)
{
if(j<B->size())
    if(A->at(i)<=B->at(j))
        original->push_back(A->at(i));
    else{
        original->push_back(B->at(j));
        i--;j++;}
}
//the ABOVE loop scans whole vector A or B.
//if there are still uncopied elements in
//the other vector, then we check for them and
//push them into original.
if(j<B->size())
    for(i=j;i<B->size();i++)
        original->push_back(B->at(i));
if(i<A->size())
    for(j=i;j<A->size();j++)
        original->push_back(A->at(j));


return EXIT_SUCCESS;
}

EDIT1: MERGE に変更を加えたので、実行時エラーはなくなりました。ただし、出力は正しくありません。誰かが問題の原因に気付いた場合は、親切に教えてください。その間、私は自分でそれを見つけようとします。

4

3 に答える 3

1

B関数内の要素が不足するとどうなりますmergeか? OOR。Bのすべての要素が の要素よりも小さい場合にテスト ケースを試し、Amerge のみを呼び出して私の意味を確認してください。

また、これは c++ です。ポインターよりも参照を使用してください。

于 2013-01-31T13:25:42.510 に答える
0

マージ関数にバグが存在します。ベクトルBまたはベクトルAが空であるかどうかをテストする必要があります。そうしないと、ベクトルへのアクセスによって例外が発生します。

于 2013-01-31T13:34:59.387 に答える
0

次の部分は間違っています:

first.assign(original->begin(),original->begin()+origL/2);
second.assign(original->begin()+origL/2+1,original->end());

Fe origL==2 の場合、最初のベクトルは { original[0] } になり、2 番目のベクトルは空になります。2 番目のベクトルのフィラーを再実装する必要があります。

second.assign(original->begin()+origL/2,original->end())
于 2013-01-31T15:07:08.360 に答える