CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 7 of 7
  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 offline Super Moderator Power Poster
    Join Date
    Jan 2003
    Location
    Hanover Germany
    Posts
    20,395

    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
    Location
    Florida
    Posts
    12,635

    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
    Location
    Florida
    Posts
    12,635

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

    Do you still have a question?

  7. #7
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,822

    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
  •  





Click Here to Expand Forum to Full Width

Featured