My Merge Sort is not working???? WHY?

This is a discussion on My Merge Sort is not working???? WHY? within the C++ Programming forums, part of the General Programming Boards category; here is the code. I get a segmentation fault every time run. Code: //Mergesort void mergesort(vector<string>& word_vector, int start, int ...

  1. #1
    Registered User
    Join Date
    Sep 2005
    Posts
    85

    My Merge Sort is not working???? WHY?

    here is the code. I get a segmentation fault every time run.

    Code:
    //Mergesort
    void mergesort(vector<string>& word_vector, int start, int stop) 
    {
       int mid;  
       if (start < stop)
       {
       	mid=(start+stop/2);
       	mergesort(word_vector, start, mid);
       	mergesort(word_vector, mid+1, stop);
       	merge(word_vector, start, mid, stop);
       }
    }
    
    void merge(vector<string>& word_vector, int start,int mid, int stop)
    {
    	int i,j,k,na,nb;
    	cout << start<< "  " << mid << "  "<< stop << endl;
    	vector<string> vector_L;
    	vector<string> vector_R;
    
    	
    	na = mid-start +1;
    	nb = stop - mid;
    		
    	for (i = 1; i <= na; i++)
    	{ 
    		vector_L.push_back(word_vector[start+i-1]);
    	}
    	for (i = 1; i <= nb; i++)
    	{
    		vector_R.push_back(word_vector[mid+1]);
    	}
    	
    	i = 1;
    	j= 1;
    	cout <<"Left Size is " << vector_L.size() << "   Right Size is " << vector_R.size() << endl;
    	for (k=start; k <= stop; k++)
    	{	cout <<"i is "<< i << "   j is  " << j <<"   k is  " << k << endl;
    		if (strcmp(vector_L[i].c_str(),vector_R[j].c_str()) < 0)
    		{
    			word_vector[k] = vector_L[i];
    			i = i + 1;
    		} 
    		else
    		{
    			word_vector[k] = vector_R[j];
    			j = j + 1;
    		
    		}
    	}
    }

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    Start by using the at member function instead of the subscript operator. You'll have an easier time of finding the problem that way.
    My best code is written with the delete key.

  3. #3
    Registered User
    Join Date
    Sep 2005
    Posts
    85
    This is for a college class ... only problem left in my program...we have to use vectors with the subscripts

  4. #4
    Registered User
    Join Date
    Jan 2005
    Posts
    7,344
    For debugging purposes, change it to at() and then change it back when you find out where you are accessing the vector incorrectly (or when you find out that you are not).

    Also check that the vector passed in has the right size, and that you are only accessing elements from 0 to size()-1.

  5. #5
    Registered User
    Join Date
    Sep 2005
    Posts
    85
    I have never used the at() how would I

  6. #6
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >we have to use vectors with the subscripts
    Well, since the subscript operator is typically unchecked, you're making your debugging job harder by using it. Who says you can't add debugging code and then change it back when you find the problem? How to use at? Change v[i] to v.at ( i ).
    My best code is written with the delete key.

  7. #7
    Registered User
    Join Date
    Sep 2005
    Posts
    85
    Ok I will, but what will this do??

  8. #8
    Registered User
    Join Date
    Sep 2005
    Posts
    85
    The error I get is
    DOING MERGE SORT
    Start 0 Stop 13
    Start 0 Stop 6
    Start 0 Stop 3
    Start 0 Stop 1
    Start 0 Stop 0
    Start 1 Stop 1


    call to merge

    0 0 1
    Left Size is 1 Right Size is 1
    i is 1 j is 1 k is 0
    terminate called after throwing an instance of 'std:ut_of_range'
    what(): vector::_M_range_check
    Aborted


    the new code is:

    Code:
    //Mergesort
    void mergesort(vector<string>& word_vector, int start, int stop) 
    {
       int mid;  
       cout << "Start " << start << "  Stop " << stop << endl; 
       if (start < stop)
       {
       	mid=(start+stop/2);
       	mergesort(word_vector, start, mid);
       	mergesort(word_vector, mid+1, stop);
       	merge(word_vector, start, mid, stop);
       }
      
    }
    
    void merge(vector<string>& word_vector, int start,int mid, int stop)
    {	
    	cout <<endl<<endl << "call to merge"<< endl << endl;
    	int i,j,k,na,nb;
    	cout << start<< "  " << mid << "  "<< stop << endl;
    	vector<string> vector_L;
    	vector<string> vector_R;
    
    	
    	na = mid-start+1;
    	nb = stop - mid;
    		
    	for (i = 1; i <= na; i++)
    	{ 
    		vector_L.push_back(word_vector.at(start+i-1));
    	}
    	for (i = 1; i <= nb; i++)
    	{
    		vector_R.push_back(word_vector.at(mid+1));
    	}
    	
    	
    	i = 1;
    	j= 1;
    	cout <<"Left Size is " << vector_L.size() << "   Right Size is " << vector_R.size() << endl;
    	for (k=start; k <= stop; k++)
    	{	cout <<"i is "<< i << "   j is  " << j <<"   k is  " << k << endl;
    		if (strcmp(vector_L.at(i).c_str(),vector_R.at(j).c_str()) < 0)
    		{
    			word_vector.at(k) = vector_L.at(i);
    			i = i + 1;
    		} 
    		else
    		{
    			word_vector.at(k) = vector_R.at(j);
    			j = j + 1;
    		
    		}
    	}
    	
    	
    
    }

  9. #9
    Registered User
    Join Date
    Sep 2005
    Posts
    85
    I have now fixed the problem with the sementation fault but I am getting in an infinate loop in the small merge function. The code is as follows:

    Code:
    //Mergesort
    void mergesort(vector<string>& word_vector, int start, int stop) 
    {
       int mid;  
       cout << "Start " << start << "  Stop " << stop << endl; 
       if (start < stop)
       {
       	mid=(start+stop/2);
       	mergesort(word_vector, start, mid);
       	mergesort(word_vector, mid+1, stop);
       	merge(word_vector, start, mid, stop);
       }
      
    }
    
    void merge(vector<string>& word_vector, int start,int mid, int stop)
    {	
    	cout <<endl<<endl << "call to merge"<< endl << endl;
    	int i,j,k,na,nb;
    	cout << start<< "  " << mid << "  "<< stop << endl;
    	vector<string> vector_L;
    	vector<string> vector_R;
    
    	
    	na = mid-start+1;
    	nb = stop - mid;
    		
    	cout << "na: " << na << "    nb: " << nb << endl;
    	
    	for (i = 1; i <= na; i++)
    	{ 
    		vector_L.push_back(word_vector.at(start+i-1));
    	}
    	for (i = 1; i <= nb; i++)
    	{
    		vector_R.push_back(word_vector.at(mid+1));
    	}
    	
    	i = 0;
    	j= 0;
    	
    	cout <<"Left Size is " << vector_L.size() << "   Right Size is " << vector_R.size() << endl;
    	cout << "Start " << start << "  Stop "<< stop << endl;
    	for (k=start; k < stop; k++)
    	{	cout <<"i is "<< i << "   j is  " << j <<"   k is  " << k << endl;
    		if (strcmp(vector_L.at(i).c_str(),vector_R.at(j).c_str()) < 0)
    		{
    			cout << endl << endl << "Trying first if" << endl;
    			word_vector.at(k) = vector_L.at(i);
    			i = i + 1;
    		} 
    		else
    		{
    			cout << endl << endl << "Trying second if" << endl;
    			word_vector.at(k) = vector_R.at(j);
    			j = j + 1;
    		
    		}
    	}
    	
    }
    The numbers it is getting stuck on are
    start = 2 stop = 3

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Jumbo Frames - sort of working
    By bj00 in forum Networking/Device Communication
    Replies: 1
    Last Post: 07-23-2007, 11:29 AM
  2. Merge Sort
    By blindman858 in forum C++ Programming
    Replies: 2
    Last Post: 05-12-2005, 12:14 PM
  3. Sorting
    By vasanth in forum A Brief History of Cprogramming.com
    Replies: 12
    Last Post: 11-10-2003, 05:21 PM
  4. Linked List Merge Sort
    By LostNotFound in forum C++ Programming
    Replies: 2
    Last Post: 03-10-2003, 08:07 PM
  5. Merge Sort Linked List Help
    By LostNotFound in forum C++ Programming
    Replies: 0
    Last Post: 02-23-2003, 08:35 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21