Click here to Skip to main content
15,892,480 members
Please Sign up or sign in to vote.
2.00/5 (1 vote)
See more:
Hi,
I'm programming a mergesort algorithm, there is a problem which i cant figure it out,
Here is my code:

C++
#include "stdafx.h"
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include "myfile.h"
using namespace std;
myfile f;
/* merge is the auxilery function of mergsort */
int merge(int a[],int p, int q, int r)
{
    f.print("\nmerge:");
    f.print(a,p,r);
    int n1=(q-p);
    int n2=(r-q);
    int * al=new int[n1];
    int * ar=new int[n2];
    for(int i=0;i<n1;i++)
	al[i] = a[p+i-1];
    for(int j=0;j<n2;j++)
	ar[j]=a[q+j];
    //al[n1+1]=-1;
    //ar[n2+1]=-1;
    int i=0;
    int j=0;
    for(int k=p;k<r;k++){
	if (al[i]<=ar[j]){
		a[k] = al[i];
		i++;
	} else {
		a[k]=ar[j];
		j++;
        }
	f.print(a,r);
    }
    return 0;
}

/* mergesort sorts an array a[0..l-1] acording to MERGESORT algorithm */
int q=0;
int mergesort(int a[],int p,int r){	
    f.print("\nmergesort:");
    f.print("\np=");f.print(p);	
    f.print("   q=");f.print(q);
    f.print("   r=");f.print(r);
    /*f.print("\n");*/f.print(a,r);	
    if(p<r){
        q=abs((p+r)/2);			
        mergesort(a,p,q);	
        mergesort(a,q+1,r);
	merge(a,p,q,r);
    }
    return 0;
}

/* getarraylenght gets the length of the array */
int getarraylength(){
	cout<<"\nPlease enter Array length ::: ";
	int l; cin>>l;	
	return l;
}

/* gettarray gets an array and pass it to be sorted */
int getarray(){
	int l=getarraylength();
	int * a = new int[l];
	cout<<"\nPlease enter array numbers ::: ";
	int i=0;
	for(i=0;i<l;i++){
		cout<<"\na["<<i<<"] ::: ";
		cin>>a[i];
	}		
	f.print(a,l);
	mergesort(a,0,l-1);
	return 0;
}
int _tmain(int argc, _TCHAR* argv[])
{
	cout<<"Main...\n";
	getarray();
	myfile f;
	/* hold the screen */ cout<<"\nEnter any key to continue ::: ";char ch;cin>>ch;
}


the array which it returns as a resault is filled with ' -33686019 '
i don't understand why.
How can i fix it?
Posted
Updated 29-Aug-14 23:28pm
v2
Comments
m.r.m.40 30-Aug-14 3:06am    
f.print
is my cout, programmed it to have the out put on the screen and in a file both in a same time.
Stefan_Lang 2-Sep-14 9:02am    
There are two objects f in your code: a global variable and another one in your main program. Is that what you meant to do? Are you sure the two instances don't conflict? E. g. if both instances try to open the same file ...

There are a couple of things that wrong here:

(1) You allocate two temporary arrays al and ar and never free them. This is a memory leak.

(2) The loop
C++
for(int i=0;i<n1;i++)>
al[i] = a[p+i-1];

picks from the wrong indices, it should be:
C++
for(int i=0;i<n1;i++)>
al[i] = a[p+i];


(3) Obviously q denotes the last element of the left range. That means that the left range contains q - p + 1 elements. Hence n1 should be
C++
int n1 = q - p + 1;
int n2 = r - q;


(4) The next loop also uses the wrong index range, it should be
C++
for(int j=0;j<n2;j++)>
ar[j]=a[q+j + 1];

And these are probably not the only things that go wrong. Why don't you simply use a debugger to step through your code and see what it does?!

And, by the way, this sorting algorithm is very inefficient. The allocation and deallocation of the auxiliary arrays takes up a lot of time. But as it probably is homework, this might be okay.
 
Share this answer
 
Well, you will have to do exactly what we would: Provide a small set of values which produce the problem and follow what is happening to them in the debugger.

Start simply: put a breakpoint on the line
C++
mergesort(a,0,l-1);
In your getarray function, and when your program stops on it, look at the data in the a array. Is it exactly what you expect? If not, why not?
If it is, step into the mergesort function and start following what the code does. Work out what should happen before you single step each line, and compare what did happen with that you think should happen. When you get a difference, you start to get the idea where the problem is.

This is a skill: and the only way to develop it is by using it. We would have to run your code and do exactly the same thing, with the added complication that you know your code, and we don't.

If you find a problem and you can't work out what causes it, then ask again - but you need to do the "donkey work" of finding where the problem might be - we can't.
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900