why i am getting Run-time error in this Merge sort algorithm code plz help
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 7 of 7

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

  1. #1
    Join Date
    May 2013
    Posts
    3

    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;
    }

  2. #2
    VictorN's Avatar
    VictorN is online now Super Moderator Power Poster
    Join Date
    Jan 2003
    Location
    Wallisellen (ZH), Switzerland
    Posts
    17,470

    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

  3. #3
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Posts
    12,121

    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.

  4. #4
    Join Date
    May 2013
    Posts
    3

    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

  5. #5
    Join Date
    May 2013
    Posts
    3

    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.

  6. #6
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Posts
    12,121

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

    Do you still have a question?

  7. #7
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,546

    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. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center