2 Replies - 524 Views - Last Post: 04 October 2012 - 10:03 AM Rate Topic: -----

#1 jamesa8  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 03-October 12

Merge and MergeSort Algorithms Problem

Posted 03 October 2012 - 11:28 PM

 
/** 
 * MERGE SORT Class to implement a sorting algorithm
 * ====================================================================
*/

#include <iostream>


using namespace std;



void Merge(int begin, int end,  int Array[], int mid) {
      // make comparitives and create subarray
       // int* ArrayTemp = new int[end];   
              // creates a temp array 
        int ArrayTemp[end] ;
        int beg = begin;                       // takes sub array and has the placehold begining
        int beg2= mid+1;                   // start of second subarray 
        int last = mid;                         // end of the first subarray
        int last2 = end;                     // end of the second subarray
        int index = beg; 
        cout<< "variables in merge initialized" ;
//do the following as long as the array isn't empty or has one number
for ( ; (beg <= last) && (beg2 <=last2 ); index++) {
        cout << "I am going through the first for loop. " ;
        if (Array[beg] < Array[beg2]){                      // if the subarray1 first is less than subarray2
           ArrayTemp[index] = Array[beg] ;          //temparray at index value will be subarray1
            beg++;              
            cout<<" I am the first if loop" ;
            //increase the value of the arraysubset1 so next comp is beg[2] vs beg2[1]
            } 
            
            
     //if the above is not true then put subarray2 value into the index of the temp array.
   else{ 
   cout<< "I am the else statement" ; 
            ArrayTemp[index] = Array[beg2]; 
            beg2++ ;
       
             }
    }
   
   //the following 2 while loops basically say if one of the subarrays is empty add the rest of 
   //the other array into the temp array. 
   cout<<"for loop has ended" ;
   while (beg <=last ) {
   cout<< "i am the first while loop " ;
            ArrayTemp[index] = Array[beg]; 
            index++; 
            beg++;
             }

    while (beg2 <= last2 ) {
            ArrayTemp[index] = Array[beg2]; 
            index++; 
            beg2++;
            cout<< "I am the second output statement" ;
            }
        
     //make index equal to the origin of the array   
    
     
     // make the array permanent. Place all values of the temp array into the actual array. 
   cout << "before transfer " <<endl; 
    for (int i = 0; i < last ;i++ ){
        Array[i] = ArrayTemp[i];
        }

} 



void MergeSort (int begin , int end,  int Array[]) { 
        //check and see if the beginning of the array is less than the end of the array
         //if so then find the middle and recursively call the function until it divies up everything. 
      cout << "begin = " << begin <<   "     end  = " << end<< endl; 
      
  
         if ( begin >= end ) {
         return; 
         cout << "bad value " ; 
         } 

else { 
               int mid = (begin+end)/2 ; 
               cout<< " mid worked" ;
                MergeSort( begin, mid, Array);   
                cout<< "merge 1 worked" ;           //recursive call keeps breaking down array
                MergeSort(mid+1, end, Array); 
                cout<<"merge2 worked" ;             // recursive call keeps breaking down array. 
                Merge ( begin, end, Array, mid);
                cout<< "merge 3 worked" ;         // merges array 
                
                cout << "i am done tranfering the temporary array to the main array" ; 
 
           } 
}

      



Hello. I have this merge sort code which I have been attempting to figure out. At first it gave me a segmentation fault but now the code is throwing out just a whole bunch of random numbers and a lot of 0's which are not even sorted properly. I have tried debugging it by placing the above cout statements, i have looked at other example code, and I have adjusted end, I have switched my static arrays to dynamic ones, and adjusted my index values to see if I was affecting those all. None of it seems to be helping. Are there any ideas or adjustments that would make it run?

Is This A Good Question/Topic? 0
  • +

Replies To: Merge and MergeSort Algorithms Problem

#2 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3631
  • View blog
  • Posts: 11,327
  • Joined: 05-May 12

Re: Merge and MergeSort Algorithms Problem

Posted 03 October 2012 - 11:48 PM

I need to look closely at the rest of the code, but at first glance, your for loop on lines 66-68 only copies half of the array because last == mid based on line 20.
Was This Post Helpful? 0
  • +
  • -

#3 jamesa8  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 03-October 12

Re: Merge and MergeSort Algorithms Problem

Posted 04 October 2012 - 10:03 AM

Hi. Thanks so much for pointing that out. I adjusted the code and ran some debugging cout statements. From what I am seeing there is a part of the code where it is rewriting the array values. Like when I put in the values 0 1 2 3 4 5 6 7 8 9 as an array input the output resulted in 0 13 32597 6299776 0 452795280 452795280 452795280. Any thoughts?
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1