Solved

My C++ with vector mergesort has run time errors, why?

Posted on 2007-03-21
6
303 Views
Last Modified: 2012-06-21
I don't understand why I'm getting run time errors in my implementation of merge sort (i have a driver program included). Could you please expalin why I'm getting memory access errors?

Also I feel like there might be an easier way to do this, I want to keep the vector data type, but I haven't worked with C++ vectors so I'm a bit confused as to whether I'm doing this correct:

Here is the code:

//-----------------------------------------------------------------------

#include <vector>
#include <iostream>
using namespace std;


void getValues(vector<int> & v);
void display(vector<int> v);

/*
mergesort takes in a vector<int> and returns a sorted vector<int>
*/
vector<int> mergesort(vector<int> list);

/*
merges two lists
*/
vector<int> merge(vector<int> left, vector<int> right);


int main()
{
      vector<int> vectorToSort;
      int value = 0;

      getValues(vectorToSort);
      display(vectorToSort);

      vector<int>  sorted =  mergesort(vectorToSort);

      display(sorted);


      system("pause");
      return 0;
}


vector<int> mergesort(vector<int> list)
{

   //one thing in the list nothing to sort
   if (list.size() < 1)
        return list;

   else
   {
         int middle = (int)list.size()/2;

         vector<int> left;
         vector<int> right;
         vector<int> * result;
            
         //copy the left half of the list to the vector left
       for(int i = 0; i < middle; i++)  
               left.push_back(list[i]);

        
       
         //copy the right half of the list to the vector right
       for(int i = middle; i < (int)list.size(); i++)
            right.push_back(list[i]);
       
         //merge sort the left and sort the right
         left = mergesort(left);
       right = mergesort(right);

         //merge them together
       result = & merge(left, right);
       
         return *result;
   }
}


vector<int> merge(vector<int> left, vector<int> right)
{  
      vector<int> result;

      int i; // used as indexing variable

      //while our lists both still have elements to merge
    while(left.size() > 0 && right.size() > 0)
      {
            //if the first element from the left <= first element from the right
            if (left[0] <= right[0])
            {
                  //add the first element from the left to result
                  result.push_back(left[0]);
                  
                  //remove the first element from left
                  i=0;vector<int> temp;
                  while(i < (int)left.size()-1)
                  {
                        
                        temp.push_back(left.back());
                        left.pop_back();
                        i++;
                  }
                  i=0;
                  while(i < (int)temp.size())
                  {
                        left.push_back(temp.back());
                        temp.pop_back();
                        i++;
                  }
            }
        else
            {
                  //else remove the first element from right
                  i=0;vector<int> temp;
                  while(i < (int)right.size()-1)
                  {
                        
                        temp.push_back(right.back());
                        right.pop_back();
                        i++;
                  }
                  i=0;
                  while(i < (int)temp.size())
                  {
                        right.push_back(temp.back());
                        temp.pop_back();
                        i++;
                  }

            }
      }      
      //if there are more elements in left part
    if (left.size() > 0 )
      {
        //add the elements of left to result
            i=0;
            while(i<(int)left.size())
                  result.push_back(left[i]);
      }

      //if there are more element in the right part
      if ((int)right.size() > 0)
      {
        //add the elements of right to result
            i=0;
            while(i<(int)right.size())
                  result.push_back(right[i]);
      }

    return result;
}


void getValues(vector<int> & v)
{
      int value = 0;
      //get values from user
      do{
            cout << "enter an integer value to put in vector, enter -1 when done: ";
            cin >> value;
            if(value!=-1)
                  v.push_back(value);
      }while(value != -1);

}

void display(vector<int> v)
{
      cout << endl << "Values in the vector are: " ;
      for(int i=0; i<v.size(); i++)
      {
            cout << v[i] << " ";
      }
      cout << endl;
}

0
Comment
Question by:polkadot
  • 3
  • 3
6 Comments
 
LVL 4

Expert Comment

by:MikeGeig
ID: 18768480
First off, mergesort and merge return vectors not vector *. So your variables result should not be a pointer. Secondly, vector.Size is not zero indexed, therefore your if statement:

if (list.size() < 1)
        return list;

Should really be

if (list.size() <= 1)
        return list;

Finally, are you able to tell at which part of your project you get the memory access error? If you can step through in a debugging process, it would make figuring it out much easier.
0
 

Author Comment

by:polkadot
ID: 18768799

Ok, well i've mad the correction, but now it seems that I have an infinite loop somewhere in the merge function, my left and right are never getting empty. I can't see why that is.

0
 
LVL 4

Expert Comment

by:MikeGeig
ID: 18768835
I will look at the merge function you have provided, if you have changed the code however, please provide me with the update
0
How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

 

Author Comment

by:polkadot
ID: 18768839
Updated Here:

//-------------------------------------

#include <vector>
#include <iostream>
using namespace std;


void getValues(vector<int> & v);
void display(vector<int> v);

/*
mergesort takes in a vector<int> and returns a sorted vector<int>
*/
vector<int> mergesort(vector<int> list);

/*
merges two lists
*/
vector<int> merge(vector<int> left, vector<int> right);


int main()
{
      vector<int> vectorToSort;
      int value = 0;

      getValues(vectorToSort);
      display(vectorToSort);

      vector<int>  sorted =  mergesort(vectorToSort);

      display(sorted);


      system("pause");
      return 0;
}


vector<int> mergesort(vector<int> list)
{

   //one thing in the list nothing to sort
   if (list.size() <= 1)
        return list;

   else
   {
         int middle = (int)list.size()/2;

         vector<int> left;
         vector<int> right;
         vector<int> result;
            
         //copy the left half of the list to the vector left
       for(int i = 0; i < middle; i++)  
               left.push_back(list[i]);

        
       
         //copy the right half of the list to the vector right
       for(int i = middle; i < (int)list.size(); i++)
            right.push_back(list[i]);
       
         //merge sort the left and sort the right
         left = mergesort(left);
       right = mergesort(right);

         //merge them together
       result =  merge(left, right);
       
         return result;
   }
}


vector<int> merge(vector<int> left, vector<int> right)
{  

      vector<int> result;

      int i; // used as indexing variable

      //while our lists both still have elements to merge
    while(left.size() > 0 || right.size() > 0)
      {
            cout << "size of left is " << left.size() << endl;
            cout << "size of right is " << right.size() << endl;
            //if the first element from the left <= first element from the right
            if (left[0] <= right[0])
            {
                  //add the first element from the left to result
                  result.push_back(left[0]);
                  
                  //remove the first element from left
                  i=0;vector<int> temp;
                  while(i < (int)left.size()-1)
                  {                        
                        temp.push_back(left.back());
                        left.pop_back();
                        i++;
                  }
                  i=0;
                  while(i < (int)temp.size())
                  {
                        left.push_back(temp.back());
                        temp.pop_back();
                        i++;
                        cout << "size of left is " << left.size() << endl;
                  }
            }
        else
            {
                  //else remove the first element from right
                  i=0;vector<int> temp;
                  while(i < (int)right.size()-1)
                  {
                        
                        temp.push_back(right.back());
                        right.pop_back();
                        i++;
                  }
                  i=0;
                  while(i < (int)temp.size())
                  {
                        
                        right.push_back(temp.back());
                        temp.pop_back();
                        i++;
                        cout << "size of right is " << right.size() << endl;
                  }

            }
      }      
      //if there are more elements in left part
    if (left.size() > 0 )
      {
        //add the elements of left to result
            i=0;
            while(i<(int)left.size())
                  result.push_back(left[i]);
      }

      //if there are more element in the right part
      if ((int)right.size() > 0)
      {
        //add the elements of right to result
            i=0;
            while(i<(int)right.size())
                  result.push_back(right[i]);
      }

    return result;
}


void getValues(vector<int> & v)
{
      int value = 0;
      //get values from user
      do{
            cout << "enter an integer value to put in vector, enter -1 when done: ";
            cin >> value;
            if(value!=-1)
                  v.push_back(value);
      }while(value != -1);

}

void display(vector<int> v)
{
      cout << endl << "Values in the vector are: " ;
      for(int i=0; i<v.size(); i++)
      {
            cout << v[i] << " ";
      }
      cout << endl;
}

0
 
LVL 4

Accepted Solution

by:
MikeGeig earned 500 total points
ID: 18768907
I am noticing a rather long trend in your merge function. plus there is a possibility for going out of bounds. If the left vector's size is empty and your referene left[0], you will effectively be out of bounds.

Try this

vector<int> merge (left, right)
{
  while(left.Size() > 0 || right.Size() > 0)
  {//make sure to check range
      if(left[0] < = right[0])
      {
            result.pushBack(left[0]);
            left.erase(left.begin());
       }
       else
      {
            result.pushBack(right[0]);
            right.erase(right.begin());
       }
  }

return result;
}


That was more or less psuedocode, but hopefully it helps you avoid so many loops, one of which is obviously infinite.
0
 

Author Comment

by:polkadot
ID: 18769079
That wasn't it, but I didn't know you could use ...erase(...begin()) like that .. so I used it instead of the mess I had with the vectors; easier to read.

Here's it is corrected:

//--------------------------------------------------
#include <vector>
#include <iostream>
using namespace std;


void getValues(vector<int> & v);
void display(vector<int> v);

//mergesort takes a vector<int> and returns a sorted vector<int>
vector<int> mergesort(vector<int> list);

//merges two vector<int>
vector<int> merge(vector<int> left, vector<int> right);


int main()
{
      vector<int> vectorToSort;
      int value = 0;

      getValues(vectorToSort);
      
      cout << "Original Vector: " << endl;
      display(vectorToSort);

      vector<int>  sorted =  mergesort(vectorToSort);

      cout << "Sorted Vector: " << endl;
      display(sorted);

      system("pause");
      return 0;
}


vector<int> mergesort(vector<int> list)
{

   //one thing in the list nothing to sort
   if (list.size() <= 1)
        return list;

   else
   {
         int middle = (int)list.size()/2;

         vector<int> left;
         vector<int> right;
         vector<int> result;
            
         //copy the left half of the list to the vector left
       for(int i = 0; i <middle; i++)  
               left.push_back(list[i]);         
       
         //copy the right half of the list to the vector right
       for(int i = middle; i < (int)list.size(); i++)
            right.push_back(list[i]);
       
         //merge sort the left and sort the right
         left = mergesort(left);
       right = mergesort(right);

         //merge them together
       result =  merge(left, right);
       
      
         return result;
   }
}


vector<int> merge(vector<int> left, vector<int> right)
{  
      vector<int> result; //the result of the merge stored here

      int i; // used as indexing variable

      //while our lists both still have elements to merge
    while(left.size() > 0 && right.size() > 0)
      {
            //if the first element on the left is smaller
            if(left[0] <= right[0])
            {
                  //move the first element on the left to result
                  result.push_back(left[0]);
                  left.erase(left.begin());

            }
            else//else the first element on the right is smaller
            {
                  //move the first element on the right to result
            result.push_back(right[0]);
            right.erase(right.begin());
            }
      }


      //if there are more elements in left part
    if (!left.empty())
      {

        //add the elements of left to result
            i=0;
            while(i< (int)left.size()){
                  result.push_back(left[i]);
                  i++;
            }

      
      }

      //if there are more element in the right part
      if (!right.empty())
      {
        //add the elements of right to result
            i=0;
            while(i< (int)right.size()){
                  result.push_back(right[i]);
                  i++;
            }
      }

    return result;
}


void getValues(vector<int> & v)
{
      int value = 0;
      //get values from user
      do{
            cout << "Enter an integer(-1 to quit): ";
            cin >> value;
            if(value!=-1 )
                  v.push_back(value);
      }while(value != -1);

}

void display(vector<int> v)
{
      cout << "[ ";
      for(int i=0; i<v.size(); i++)
      {
            cout << v[i] << " ";
      }
      cout << "]" << endl;
}

0

Featured Post

How to improve team productivity

Quip adds documents, spreadsheets, and tasklists to your Slack experience
- Elevate ideas to Quip docs
- Share Quip docs in Slack
- Get notified of changes to your docs
- Available on iOS/Android/Desktop/Web
- Online/Offline

Join & Write a Comment

Often, when implementing a feature, you won't know how certain events should be handled at the point where they occur and you'd rather defer to the user of your function or class. For example, a XML parser will extract a tag from the source code, wh…
IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article loc…
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…

708 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

16 Experts available now in Live!

Get 1:1 Help Now