Ç - 合并合并排序的一部分 [英] C - merge part of merge sort
问题描述
我是新合并排序和我试图创建一个。我归并排序没有排序我送这阵，我想不通为什么。这里是所有code
I am new to merge sorts and am trying to create one. My merge sort is not sorting the array I am sending it and I can't figure out why. here is a link to all of the code http://pastebin.com/M4RUzhUa
下面是我的归并功能
void merge_sort(int array[], int low, int high) {
int middle = (low + high) / 2;
if(low < high) {
merge_sort(array, low, middle);
merge_sort(array, middle+1, high);
merge(array, low, middle, high);
}
}
下面是我的（更新）合并功能
Here is my (updated) merge function
void merge(int array[], int low, int middle, int high) {
int size,left,right,i, j;
size = high - low + 1;
int array1[high];
left = low;
right = middle + 1;
i = low;
while ((left<=middle) && (right<=high)) {
if(array[left] < array[right]) {
array1[i] = array[left];
left++;
i++;
}
else {
array1[i] = array[right];
right++;
i++;
}
}
while (left <= middle) {
array1[i] = array[left];
left++;
i++;
}
while (right <= high) {
array1[i] = array[right];
right++;
i++;
}
for (j = low; j < i; j++) {
array[j] = array1[j];
}
}
在我的程序输入数组是
9
3
2
1
5
9 3 2 1 5
和输出
0
1
2
3
5
0 1 2 3 5
东西与我想不通的第一要素发生
something is happening with the first element that i can't figure out
推荐答案
更新的code新评论：
New comments for updated code:
它看起来像你过去华尔兹阵列的结尾。来测试的一种方法是添加在你的阵列的一些后卫的变量，像这样的：
It looks like you are waltzing past the end of your array. A way to test that would be to add some guard variables around your array, like this:
#define NUM_OF_INTS 5
#define DEBUG 1
int main()
{
int frontguard=-500;
int numbers[NUM_OF_INTS];
int backguard=-600;
int i;
srand(0);
//Fill the array
for( i = 0; i < NUM_OF_INTS; i++ )
{
//Use random numbers
//numbers[i] = rand()%10000;
//Use reverse sorted list
numbers[i] = NUM_OF_INTS-i;
//Use sorted list
//numbers[i] = i;
}
if (DEBUG == 1) printf( "Unsorted list\n" );
if (DEBUG == 1) printarray( numbers, 0, NUM_OF_INTS/2, NUM_OF_INTS );
if (DEBUG == 1) printf( "frontguard=%04d, backguard=%04d\n", frontguard, backguard);
merge_sort( numbers, 0, NUM_OF_INTS );
if (DEBUG == 1 ) printf( "\nSorted list\n");
if (DEBUG == 1) printarray( numbers, 0, NUM_OF_INTS/2, NUM_OF_INTS );
if (DEBUG == 1) printf( "frontguard=%04d, backguard=%04d\n", frontguard, backguard);
return 0;
}
printarray 是一个辅助的功能，我写信给prettyprint什么是在一个阵列发生
printarray is a helper function I wrote to prettyprint what is happening in an array
void printarray( const int arr[], const int low, const int middle, const int high )
{
int i;
for (i = low; i < high; i++ )
{
if( i == low )
printf( " L%04d", i );
else if( i == middle )
printf( " M%04d", i );
else if( i == (high-1) )
printf( " H%04d", i );
else
printf( " *%04d", i );
}
printf( "\n" );
for( i = low; i < high; i++ )
printf( " %04d", arr[i] );
printf( "\n" );
}
这是共同的需要创建一些辅助调试功能，如这让你的code工作，如果你没有/想要一个调试器。不要害怕写一些扔掉的code，了解你的code是干什么！在这种情况下，我并不需要L / M / H的路线，但它仍然是值得花时间。我建议您在code离开这些类型的功能，注释掉（使用＃定义诸如DEBUG），以备将来的维护人员需要它们。
It is common to have to create some helper debug functions such as this to get your code working if you do not have/want a debugger. Do not be afraid to write some throw-away code to understand what your code is doing! In this case, I didn't need the line of L/M/H, but it is still worthwhile to spend the time. I recommend leaving these types of functions in your code, commented out (using a #define such as DEBUG), in case a future maintainer needs them.
下面是你的函数的输出作为-是：
Here is the output of your function as-is:
Unsorted list
L0000 *0001 M0002 *0003 H0004
0005 0004 0003 0002 0001
frontguard=-500, backguard=-600
Sorted list
L0000 *0001 M0002 *0003 H0004
-600 0001 0002 0003 0004
frontguard=-500, backguard=0005
您可以看到 backguard 得到了覆盖，抢到你的输出。 （这种行为可以在不同的CPU架构，C实现不同，运行细节，顺便说一句。）问题是，你叫 merge_sort 从的main（） 与高作为数组（5在这种情况下）的大小，但 merge_sort 预计高是在数组中的最后一个有效的索引（编号[4]是最后一个数组项）。修改的main（）到
You can see that the backguard got overwritten and "stolen" into your output. (This behavior can differ on different CPU architectures, C implementations, and run specifics, btw.) The problem is that you call merge_sort from main() with high as the size of the array (5 in this case), however merge_sort expects high to be the last valid index in the array (numbers[4] is the last array item). Modify main() to
merge_sort( numbers, 0, NUM_OF_INTS-1 );
和测试它反对排序，反向排序，和数字的随机排列。
and test it against a sorted, reverse sorted, and random array of numbers.
原创评论：
Original comments:
嗯，首先，你应该收到segementation故障，不只是排序不正确的数据。
Well, first off, you should be receiving a segementation fault, not just incorrectly sorted data.
size = high - low + 1;
//create a helper array and set it equal to the input array
int array1[size];
for (i = low; i <= high; i++) {
array1[i] = array[i];
}
想想这里发生的事情是不为零时低。比方说，L = 6，M = 6，H = 7。你是你的助手数组的大小设置为2，但你与我访问它= 6，所以你捣毁堆栈。
Think about what happens here when low is not zero. Let's say l=6, m=6, h=7. You are setting the size of your helper array to 2, but you are accessing it with i=6, so you are trashing the stack.
对于最简单的解决方法是申报 INT数组1（高）; 。它的内存效率很低，但它使code简单的休息，这确实是更有价值的。
The easiest fix for this is to declare int array1[high];. It's memory inefficient but it keeps the rest of the code simple, which is really more valuable.
二，你的for循环索引过去数组的末尾，你需要使用I＆LT;高。在C语言中，数组从0开始，因此大小5的阵列具有0,1,2,3,4有效位置。您code原样将试图从阵列中读取数据[5]（可能不是致命的），并写信给ARRAY1 [5]（很可能是致命的）。我敢打赌，这是为什么你在尺寸语句+1，因为你过去的推进，否则ARRAY1的结尾。
Second, your for loop is indexing past the end of array, you need to use i < high. In C, arrays start at 0, so an array of size 5 has valid locations at 0,1,2,3,4. Your code as-is would try to read from array[5] (probably not fatal), and write to array1[5] (very possibly fatal). I'll bet this why you have a +1 in the size statement, since you were advancing past the end of array1 otherwise.
for (i = low; i < high; i++) {
这将解决您的分段错误。与固定的，你仍然得到在输出垃圾数据。
These will fix your segmentation fault. With that fixed, you are still getting garbage data in your output.
您还有中间，if语句永远不会被执行 - 任何等效的数据将会被覆盖的第一个if语句
Your middle else-if statement is never going to be executed - any equivalent data is going to be covered by the first if statement.
您while循环没有正确处理退化情况。它需要检测，如果其中一个列表中已被完全消耗，并且如果是这样，只复制其他列表的其余部分。
Your while loop does not properly handle the degenerate cases. It needs to detect if one of the two lists has been completely consumed, and if so, just copy the rest of the other list.
另外，虽然循环需要为低，中分离跟踪变量和输出数组。您不能使用currentLow为低，输出数组。
Also, the while loop needs separate tracker variables for low, mid, and the output array. You cannot use currentLow for both low and the output array.
最后，测试排序时，随机数据是不够的（尤其是大小为5），你应该总是测试排序和反向排序列表的完全退化情况。
Finally, when testing sorting, random data is not sufficient (esp. with a size of 5), you should always test the totally degenerate cases of a sorted and reverse-sorted lists.
这篇关于Ç - 合并合并排序的一部分的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
