使用随机向量帮助mergesort！ [英] Help with mergesort with a random vector!
问题描述
到目前为止，我将此作为我的代码
#include< iostream>
#include< vector>
#include< ctime>
#include< cstdlib>
using namespace std;
void merge（vector< int> aVector，int size，int low，int middle，int high）{
int temp [size];
for（int i = low; i< = high; i ++）{
temp [i] = aVector [i];
}
int i = low;
int j = middle + 1;
int k = low;
while（i< = middle&& j< = high）{
if（temp [i]< = temp [j]）{
aVector [k] = temp [i];
++ i;
}
else {
aVector [k] = temp [j];
++ j;
}
++ k;
}
while（i< = middle）{
aVector [k] = temp [i];
++ k;
++ i;
}
}
void mergeSort（vector< int> aVector，int size，int low，int high）{
if（low< high）{
int middle =（低+高）/ 2;
mergeSort（aVector，size，low，middle）;
mergeSort（aVector，size，middle + 1，high）;
合并（aVector，大小，低，中，高）;
}
}
int main（）
{
const int size = 10;
vector< int> aVector;
srand（（无符号）时间（NULL））;
for（int i = 0; i< 10; i ++）{
int b = rand（）％9 + 1;
aVector.push_back（b）;
cout<< aVector [i]<< ;
mergeSort（aVector，size，0,10）;
}
返回0;
}
我只有一半了解mergeSort并且不足以使用随机向量。所以这段代码使得.exe停止工作是否有我可以解决的部分或我必须以不同的角度处理这个问题？
我有什么尝试过：
我尝试使用谷歌搜索并浏览了许多不同的mergeSort示例，但没有一个真正适用于矢量和少数确实有简单的已设置向量。我找不到一个随机向量。
好的，你已经编写了一些代码并且它没有做你想要的或者 - 就像你的情况一样 - 甚至没有编译。在这种情况下，您需要在调试器中运行程序或理解编译器提供给您的错误消息。当你第一次这样做时，这并不容易，但通过一些练习会变得更容易。谷歌搜索遇到同样麻烦的其他人也无济于事。
那就是说，让我们系统地开始吧。首先要重新阅读你的课程笔记并完全理解它们。您甚至可以通过阅读合并排序 - 维基百科，免费百科全书等文章来获得更广阔的视野[ ^ ]。
我不会为你做这项工作，因为这肯定是一项练习，你应该通过这样做来学习。但是我会给你一些提示：
void merge（vector< int> aVector ， int size， int low， int middle， int high）
< / int>
size参数实际上是多余的。 aVector可以通过size（）成员函数告诉你它的大小。通过第二次传递大小只会犯错误的空间。
{
int temp [size];
这不起作用。它甚至不会编译。它肯定不是很有效率。如果您需要一个临时数组（并且您使用合并排序算法），最好在mergeSort函数中分配一次并将其传递给每次合并调用。您可以使用另一个向量< int>对于临时数组。
int middle =（low + high ）/ 2 ;
mergeSort（aVector，size，low，middle）;
mergeSort（aVector，size，middle + 1，high）;
在整个程序中使用相同的约定。您首先将低值定义为范围的第一个元素，将高值定义为超出范围。这是C / C ++中非常常见的做法。现在看看你对mid的定义：第一次调用mergeSort会将该范围从低到排序，不包括中。你看到你犯了什么错误？
看看你所有的循环并检查它们是否应该包括或排除最终值，即你是否需要与< =或< ;.进行比较仔细检查每个循环！
在调试器中运行程序并在每个语句处停止。通过查看变量来检查你的程序是否完全符合预期。
我希望这些提示可以帮助你找到正确的方法。
编程时，第一步是了解你的编程。
合并排序 - 维基百科，免费的百科全书 [ ^ ]
查看图形。
随机向量只是一个你不知道值的向量。难度在哪里？
显然，你自己的代码对你来说就像一个黑盒子。它不符合你的期望，你不明白为什么。
以下内容不是直接解决你的问题，而是一个能帮助你自己理解错误的关键。
调试器是你的朋友。它将向您显示您的代码实际正在做什么。
按照执行，检查变量，您将看到有一个点，它停止做您期望的。
掌握Visual Studio 2010中的调试 - 初学者指南 [< a href =http://www.codeproject.com/Articles/79508/Mastering-Debugging-in-Visual-Studio-A-Beginntarget =_ blanktitle =New Window> ^ ]
建议：
- 你可以在你的代码中加注释。
- 保持一致！
第一次调用
，10是最后一行+ 1，到处都是一样！
mergeSort（aVector，size ， 0 ， 10 ）;
< pre lang =c ++> mergeSort（aVector，size，low，middle）;
mergeSort（aVector，size，middle+1，high）;
你需要学习C ++数组并理解第一行是0和最后一行是size-1。
这只是你遇到的一些问题。
我的建议：在调试器上逐行运行程序检查每个变量的变化步骤，您将看到它没有按预期运行的位置。
so far I have this as my code
#include <iostream>
#include <vector>
#include <ctime>
#include <cstdlib>
using namespace std;
void merge(vector<int> aVector, int size, int low, int middle, int high){
int temp[size];
for(int i = low; i <= high; i++){
temp[i] = aVector[i];
}
int i = low;
int j = middle+1;
int k = low;
while (i <= middle && j <= high){
if(temp[i] <= temp[j]){
aVector[k] = temp[i];
++i;
}
else {
aVector[k] = temp[j];
++j;
}
++k;
}
while (i <= middle){
aVector[k] = temp[i];
++k;
++i;
}
}
void mergeSort(vector<int> aVector, int size, int low, int high){
if (low < high){
int middle = (low + high) / 2;
mergeSort(aVector, size, low, middle);
mergeSort(aVector, size, middle+1, high);
merge(aVector, size, low, middle, high);
}
}
int main()
{
const int size = 10;
vector<int> aVector;
srand((unsigned)time(NULL));
for (int i = 0; i < 10; i++) {
int b = rand() % 9 + 1;
aVector.push_back(b);
cout << aVector[i] << " ";
mergeSort(aVector, size, 0, 10);
}
return 0;
}
I only half understand mergeSort and not enough to do it with a randomized vector. So this code makes the .exe stop working is there a part I can fix or do I have to approach this in a different angle?
What I have tried:
I've tried googling and going through many different examples of mergeSort but none of them really work with vectors and the few that do have very simple already set vectors. I can't find one for a randomized vector.
Okay, you have written some code and it doesn't do what you want or - as in your case - doesn't even compile. In this case you need to run your program in a debugger or understand the error messages the compiler is giving you. That is not easy when you are doing it the first time, but it will become easier with some practice. Googling for others that ran into the same trouble will not help you.
That said, let's start systematically. First start be re-reading your course notes and understanding them FULLY. You might even get a wider perspective by reading articles like this one Merge sort - Wikipedia, the free encyclopedia[^].
I won't do the work for you, as this is certainly an exercise and you should learn by doing it. But I am going to give you a couple of hints:
void merge(vector<int> aVector, int size, int low, int middle, int high) </int>
The size argument is actually superfluous. aVector can tell you its size by the size() member function. By passing the size a second time gives only room to make mistakes.
{ int temp[size];
This will not work. It won't even compile. And it certainly is not very efficient. If you need a temporary array (and you do for the merge sort algorithm), better allocate it once in your mergeSort function and pass it to every call of merge. You may use another vector<int> for the temporary array.
int middle = (low + high) / 2; mergeSort(aVector, size, low, middle); mergeSort(aVector, size, middle+1, high);
Use the same conventions throughout your program. You started by defining low as the first element of the range and high as the first element beyond the range. That is a very common practice in C / C++. Now look at your definition of middle: The first call to mergeSort will sort that range from low up to and not including middle. You see where you made a mistake?
Take a look at all of your loops and check whether they should up and including or excluding the final value, i.e. whether you need to compare with <= or <. Double check each and every loop!
Run your program in a debugger and stop at every single statement. Check whether your program did exactly what you expected it to do by looking at the variables.
I hope these hints will get you on the right way.
When programming, the first step is to understand what you program.
Merge sort - Wikipedia, the free encyclopedia[^]
look at the graphics.
Randomized vector is just a vector with values that you don't know. where is the difficulty ?
Obviously, your own code is like a blackbox to you. It don't do what you expect, and you don't understand why.
What follow is not directly a solution to your problem, but a key that will help you to understand by yourself what is wrong.
The debugger is your friend. It will show you what your code is really doing.
Follow the execution, inspect variables and you will see that there is a point where it stop doing what you expect.
Mastering Debugging in Visual Studio 2010 - A Beginner's Guide[^]
Advices:
- you can put comments in your code.
- be consistent!
in first call, 10 is last row+1, do the same everywhere !
mergeSort(aVector, size, 0, 10);
mergeSort(aVector, size, low, middle); mergeSort(aVector, size, middle+1, high);
You need to study C++ arrays and understand that thefirst rowis0andlast rowissize-1.
It is only a few problems you have.
My advice: run the program line by line on debugger inspect variables changes on every step and you will see where it don't behave as expected.
这篇关于使用随机向量帮助mergesort！的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
