# why i am getting Run-time error in this Merge sort algorithm code plz help

Printable View

• May 3rd, 2013, 01:42 AM
contest_contest
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;
}
• May 3rd, 2013, 04:02 AM
VictorN
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
• May 3rd, 2013, 07:27 AM
GCDEF
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.
• May 3rd, 2013, 01:07 PM
contest_contest
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
• May 3rd, 2013, 01:10 PM
contest_contest
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.
• May 3rd, 2013, 01:15 PM
GCDEF
Re: why i am getting Run-time error in this Merge sort algorithm code plz help
Do you still have a question?
• May 3rd, 2013, 01:17 PM
2kaud
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?