2 Replies - 383 Views - Last Post: 04 October 2012 - 09:45 PM Rate Topic: -----

#1 jamesa8  Icon User is offline

  • New D.I.C Head

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

MergeSort

Posted 04 October 2012 - 06:39 PM

#include <iostream>  	
#include <stdlib.h>
#include <stdio.h>
#include <vector>				// provides Vector
#include <algorithm>        	// provides built-in sort
#include <sys/times.h>			// provides tms timing struct
#include <assert.h>
#include "LList.cpp"	
#include "Merge.cpp"		// include your sorting LList class

using namespace std;	

struct tms  tmsstart, tmsend;	// tms is declared in sys/times.h
								// tmsstart & tmsend are structures to hold timing info
								

// Global settings
struct gA_t {
    int alg;        	// -a algorithm 
    int min;			// -m min n
    int max;			// -x max n
    float scale;		// -s scaling factor between steps
} gA;

/* 
 * Displays program usage
 */
void displayUsage(){
	cout << "Usage: mySort [OPTION]...\n\n";
	cout << "Time different sort algorithms with lists of various sizes.\n";
	cout << "  -a <int>	Algorithm to use.\n";
	cout << "  -m <int>	Starting list size\n";
	cout << "  -x <int>	Ending list size\n";
	cout << "  -s <float> Scaling factor\n\n";
}

/* 
 * Prints the number of seconds elapsed between the stored times in tmsstart
 * 	and tmsend;
 */
void printTime(){
	long clktck = sysconf(_SC_CLK_TCK);
    printf("%f",
            (tmsend.tms_utime - tmsstart.tms_utime) / (double) clktck);
}

/**
 * Main for program.  
 */
int main(int argc, char* argv[]) { 
	gA.alg = 1;				// Set defaults
	gA.min = 20;
	gA.max = 1000;
	gA.scale = 2.0;
	int val = gA.min;			
    int j;
    int array[val];
//sets array 
for(int i = 0; i <= val; i++){
		array[i] = rand() % 200;
		j=i;
			}
//sorts array
	MergeSort (begin, end, array ) ;
	
//the following prints the array 
        for (int i = 0; i <= end ;i++ ){
             cout << array[i] << endl; 
               }

			//assert(isSorted(??));	// good idea to make sure it's really sorted
		
		// fill in rest of cases and sort algorithms here
		// ...
		
		
			// print size and execution time		printTime();

	return 0;
}

 


This is the Main program above. It calls the MergeSort function and it then references the following.

 
#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 beg =0 ;                       // 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; 
      
//do the following as long as the array isn't empty or has one number

while( (beg <= last) && (beg2 <= last2 )){
  
        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++;                     //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{ 
            ArrayTemp[index] = Array[beg2]; 
            beg2++ ;     
             }
             index ++;
    }
   
   //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. 
   
   while (beg <= last ) {
 cout <<"while loop active" <<endl;
            ArrayTemp[index] = Array[beg]; 
            index++; 
            beg++;
             }

    while (beg2 <= last2 ) {
    cout <<"while loop active 1" <<endl;
            ArrayTemp[index] = Array[beg2]; 
            index++; 
            beg2++;          
            }
        
     //make index equal to the origin of the array   
    
     
     // make the array permanent. Place all values of the temp array into the actual array. 
  
    for (int i = 0; i <= end ;i++ ){
        Array[i] = ArrayTemp[i];
        }
        
delete [] ArrayTemp;
} 



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.       
         if ( begin >= end) {
            return; }

          else { 
                int mid; 
                mid = (begin+end)/2 ;              
                MergeSort( begin, mid, Array);     //recursive call keeps breaking down array                            
                MergeSort(mid+1, end, Array);     // recursive call keeps breaking down array. 
                Merge ( begin, end, Array, mid);
         }  
} 


The issue is that the merge function sorts like 99.9 percent of the items passed but it keeps missing one or two. For example if the system passes the values 183 86 177 115 193 135 186 92 49 21 162 27 90 59 163 126 140 26 172 136 11 the output is not coming out the way it should. Instead the output is 26 27 49 59 86 90 91 126 135 136 140 162 163 172 177 183 115 186 21 193. Clearly 21 and 115 are not greater than 177 but I do not understand where the issue is. I have checked the while loops and thrown cout statements in every section of the code (taken out to make easy readability) but I am at a loss. Would anyone have ANY ideas whatsoever. This would be entirely helpful. Thanks so much !

Is This A Good Question/Topic? 0
  • +

Replies To: MergeSort

#2 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 352
  • View blog
  • Posts: 770
  • Joined: 27-June 09

Re: MergeSort

Posted 04 October 2012 - 07:13 PM

Go through and check all your indexes. I noticed this one.
for (int i = 0; i <= end ;i++ ){
	        Array[i] = ArrayTemp[i];
	        }

"i" should start at "begin". Nothing is initialized in ArrayTemp before begin so this code should be writing random values into Array from ArrayTemp. I'm not sure how it is producing valid output.

EDIT - I just noticed this
int beg =0 ;

It should also be "begin" and not 0. Basically make sure your first array contains values from "begin" to "mid" and your second array contains values from "m+1" to "end". Then write to the array from "begin" to "end"

This post has been edited by mojo666: 04 October 2012 - 07:27 PM

Was This Post Helpful? 1
  • +
  • -

#3 jamesa8  Icon User is offline

  • New D.I.C Head

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

Re: MergeSort

Posted 04 October 2012 - 09:45 PM

It worked. Thank you so much you are amazing ! I never would have thought of that. You have made my day.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1