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;
}
Re: why i am getting Run-time error in this Merge sort algorithm code plz help
I guess there is a bug in you code. Unfortunately, I cannot say you more because the code snippet you have posted is absolutely unreadable! Please, repost it using Code tags and proper indentations!
Besides, you have to debug your code to check whether your algorithms is correct and whether some other problems (like rRun-time error) exist
Re: why i am getting Run-time error in this Merge sort algorithm code plz help
Yeah, format your code and run it in the debugger.
It didn't crash for me, but I don't know what you used for input.
Re: why i am getting Run-time error in this Merge sort algorithm code plz help
http://uva.onlinejudge.org/external/2/299.html
This a a on-line judge problem .the main goal of this code finding number of swap to sort .i used here merge sort algorithm
example input:
3 /number of input file
3 /number of input
1 3 2 /inputted number
4 /number of swap
4 3 2 1 same here
2
2 1
Re: why i am getting Run-time error in this Merge sort algorithm code plz help
http://uva.onlinejudge.org/external/2/299.html
This a a on-line judge problem .the main goal of this code finding number of swap to sort .i used here merge sort algorithm
example input:
3 /number of input file
3 /number of input
1 3 2 /inputted number
4
4 3 2 1
2
2 1
output:
Optimal train swapping takes 1 swaps.
Optimal train swapping takes 6 swaps.
Optimal train swapping takes 1 swaps.
Re: why i am getting Run-time error in this Merge sort algorithm code plz help
Do you still have a question?
Re: why i am getting Run-time error in this Merge sort algorithm code plz help
Using your data under Windows VS - this works OK for me. 1 3 2 produces 1 swap, 4 3 2 1 produces 6 swaps, 2 1 produces 1 swap.
What compiler/OS are you using?