merge sort problem

Hi,
I'm programming a mergesort algorithm, there is a problem which i cant figure it out,
Here is my code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#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?
1. You need to look at your merge ranges.
2. Why is that q global? It breaks the recursion.

Run this and look at the output. It's your code that just shows the parameters to the merge functions.

What should the output be and how does it differ from what your program produces?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <cstdlib>

using namespace std;

/* merge is the auxilery function of mergsort */
int merge(int a[],int p, int q, int r) {
	cout << "merge(p=" << p << ", q=" << q << ", r=" << r << ")" << endl;

	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];

	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++;
		}
	}
	return 0;
}

/* mergesort sorts an array a[0..l-1] acording to MERGESORT algorithm */
int q=0; // WHY IS THIS GLOBAL?
int mergesort(int a[],int p,int r) {
	cout << "mergesort(p=" << p << ", q=" << r << ")" << endl;

	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];
	}

	mergesort(a,0,l-1);
	return 0;
}

int main(int argc, char* argv[])
{
	cout<<"Main...\n";
	getarray();
	/* hold the screen */ cout<<"\nEnter any key to continue ::: ";char ch;cin>>ch;
}
Last edited on
Registered users can post here. Sign in or register to post.