Merge_sort，比较的问题 [英] Merge_sort, a problem with comparison

问题描述

我正在编写一个mergesort算法，有一个问题我无法弄清楚，

这是我的代码：

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

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

它返回的阵列充满'-33686019'

i不明白为什么。

如何修复它？

the array which it returns as a resault is filled with ' -33686019 '
i don't understand why.
How can i fix it?

推荐答案

这里有一些错误：



（1）你分配两个临时数组al和ar，永远不会释放它们。这是一个内存泄漏。



（2）循环

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

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

从错误的指数中选择，它应该是：

picks from the wrong indices, it should be:

for(int i=0;i<n1;i++)>
al[i] = a[p+i];

（3）显然q表示左范围的最后一个元素。这意味着左范围包含q - p + 1个元素。因此n1应该是

(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

int n1 = q - p + 1;
int n2 = r - q;

（4）下一个循环也使用错误的索引范围，它应该是

(4) The next loop also uses the wrong index range, it should be

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.

嗯，你必须完全按照我们的意愿去做：提供一小组产生问题的值并跟踪发生的事情在调试器中给他们。



简单地说：在线上放一个断点

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

mergesort(a,0,l-1);

在 getarray 函数中，当程序停止运行时，查看中的数据a 数组。这正是你期望的吗？如果没有，为什么不呢？

如果是，请进入 mergesort 函数并开始关注代码的作用。找出在单步执行每一行之前应该发生的事情，并比较您认为应该发生的事情。当你得到不同之处时，你会开始明白问题所在。



这是一项技能：开发它的唯一方法就是使用它。我们必须运行你的代码并做同样的事情，增加的复杂性是你知道你的代码，而我们没有。



如果你找到了问题，你无法弄清楚是什么导致它，然后再问 - 但你需要做驴工作找到问题所在 - 我们不能。

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.

这篇关于Merge_sort，比较的问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！