Solved

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

Posted on 2007-03-21
6
313 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 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
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 

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

Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Unlike C#, C++ doesn't have native support for sealing classes (so they cannot be sub-classed). At the cost of a virtual base class pointer it is possible to implement a pseudo sealing mechanism The trick is to virtually inherit from a base class…
Introduction This article is a continuation of the C/C++ Visual Studio Express debugger series. Part 1 provided a quick start guide in using the debugger. Part 2 focused on additional topics in breakpoints. As your assignments become a little more …
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

734 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