Solved

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

Posted on 2007-03-21
6
307 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
Gigs: Get Your Project Delivered by an Expert

Select from freelancers specializing in everything from database administration to programming, who have proven themselves as experts in their field. Hire the best, collaborate easily, pay securely and get projects done right.

 

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

Gigs: Get Your Project Delivered by an Expert

Select from freelancers specializing in everything from database administration to programming, who have proven themselves as experts in their field. Hire the best, collaborate easily, pay securely and get projects done right.

Question has a verified solution.

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

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…
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 viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

785 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