-
May 3rd, 2013, 01:42 AM
#1
why i am getting Run-time error in this Merge sort algorithm code plz help
# include <iostream>
# include <vector>
# include <cstdio>
# include <algorithm>
# define inf 100000
using namespace std;
int cnt;
vector<int> merge( vector<int>& left, vector<int>& right)
{
vector<int> result;
result.clear();
int ll=left.size(), rl=right.size();
int i = 0, j = 0, limt=ll+rl;
left.push_back(inf);
right.push_back(inf);
for(int k=0;k<limt;k++)
{
if(left[i] <=right[j])
{
result.push_back(left[i]);
i++;
}
else
{
result.push_back(right[j]);
j++;
cnt+=(ll-i);
}
}
return result;
}
vector<int> merge_sort(vector<int>& vec)
{
if(vec.size() == 1) return vec;
vector<int>::iterator middle =vec.begin()+(int)(vec.size() / 2);
vector<int> left(vec.begin(), middle);
vector<int> right(middle, vec.end());
left = merge_sort(left);
right = merge_sort(right);
return merge(left, right);
}
int main()
{
int n,x,kase;
cin>>kase;
while(kase--)
{
cin>>n;
vector<int>v;
v.clear();
cnt=0;
for(int i=0;i<n;i++)
{
cin>>x;
v.push_back(x);
}
vector<int> res=merge_sort(v);
cout<<"Optimal train swapping takes "<<cnt<<" swaps."<<endl;
}
return 0;
}
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|