Solved

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

Posted on 2007-03-21
6
306 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
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 

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

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

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

Suggested Solutions

When writing generic code, using template meta-programming techniques, it is sometimes useful to know if a type is convertible to another type. A good example of when this might be is if you are writing diagnostic instrumentation for code to generat…
Container Orchestration platforms empower organizations to scale their apps at an exceptional rate. This is the reason numerous innovation-driven companies are moving apps to an appropriated datacenter wide platform that empowers them to scale at a …
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…

932 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

12 Experts available now in Live!

Get 1:1 Help Now