-
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;
}
-
May 3rd, 2013, 04:02 AM
#2
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
Victor Nijegorodov
-
May 3rd, 2013, 07:27 AM
#3
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
#4
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
#5
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
#6
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
#7
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?
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
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
|