Solved

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

Posted on 2007-03-21
6
310 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
Industry Leaders: 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

On Demand Webinar - Networking for the Cloud Era

This webinar discusses:
-Common barriers companies experience when moving to the cloud
-How SD-WAN changes the way we look at networks
-Best practices customers should employ moving forward with cloud migration
-What happens behind the scenes of SteelConnect’s one-click button

Question has a verified solution.

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

C++ Properties One feature missing from standard C++ that you will find in many other Object Oriented Programming languages is something called a Property (http://www.experts-exchange.com/Programming/Languages/CPP/A_3912-Object-Properties-in-C.ht…
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
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 viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.

730 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