在没有数组崩溃的情况下合并排序 [英] Merge sort without arrays crashing
问题描述
亲爱的，
我有一个明智的想法，即在不递归创建数组的情况下进行合并排序代码（显然不是链表）。逻辑似乎是正确的，每个变量的行为应该除了一个，我似乎无法弄清楚为什么。我希望有人有时间来帮助我。
我会编写一个单独的程序，对链接列表进行合并排序但是在这里，我想克服合并排序的主要弱点在额外的开销方面，所以我决定尝试这个。
请看下面的代码：
Dear all,
I got the bright idea to do a merge sort code without creating arrays recursively (obviously not linked lists). The logic seems to be right and every variable behaves as it should except one, and I just can't seem to figure out why. I hope someone has some time to help me.
I will write a separate program that does merge sort on linked lists but here, I wanted to overcome merge sort's main weakness in terms of the extra overhead so I decided to experiment with this.
Please see the code below:
/* includes and macros */
// required for input / output with minGW GCC
#include <stdio.h>
#define printf __mingw_printf
// required for the dynamic storage allocation and the random integer generator functions
#include <stdlib.h>
// required for the time function, which is required for rand() to work properly
#include <time.h>
/* type definitions (structs go here) */
/* global declarations */
static unsigned short n = 0;
/* function prototypes */
void swapSort (int *, int *);
void mergeSort (int []);
/* main function */
int main ()
{
/* some initial declarations & initializations */
// ask the user for the amount of integers to sort
printf("How many integers do you want sorted by Merge Sort? ");
scanf("%hu", &n);
// for rand()
srand(time(NULL));
// array input
int arrayInput[n];
/* array input */
// input taken from the rand() function
printf ("\n");
for (register unsigned short i = 0; i <= n-1; i++)
arrayInput[i] = rand();
// printing the input so the user knows exactly what rand() produced
printf ("\n");
for (register unsigned short i = 0; i <= n-1; i++)
printf ("[%d] ", arrayInput[i]);
printf ("\n");
/* sort the list by Merge Sort */
mergeSort(arrayInput);
/* print the sorted array */
printf("\n");
for (register unsigned short i = 0; i <= n-1; i++)
printf("[%d] ", arrayInput[i]);
printf("\n");
/* exit main and the program */
return 0;
}
/* function definitions */
/* simple swapping function */
void swapSort (int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
/* the Merge Sort function, improving upon bubble sort */
void mergeSort (int mainArray[])
{
// sort the subarrays formed by every two elements, then by every four elements, then by 8, etc.
for (unsigned short sizeSubArr = 2; sizeSubArr <= n;) // set the outer loop so that it sorts all the subarrays of a specific size; the subarray size will change per iteration
// of the loop so there may be a remainder subarray of a different size than sizeSubArr
SubArrayMarkers:
{
unsigned short total_number_of_subarrays = n / sizeSubArr;
unsigned short remSizeSubArr = n % sizeSubArr;
unsigned short subArrLen = sizeSubArr;
for (unsigned short mainIndex = 0, subArrNo = 1; subArrNo <= total_number_of_subarrays; mainIndex++) // a loop that marks the beginning of each subarray as it goes through
// the main array and then the subarray is sorted by this loop's inner loops
// it also keeps track of the index of the main array
{
BubbleSort:
for (unsigned short j = 0; j <= n; j = 0) // this is where bubble sort starts, with the infinite outer loop to be broken if there are no swaps done within the bubble sort
// we set l to mainIndex so that if there are multiple iterations of bubble sort, it doesn't screw up mainIndex
{
unsigned short l = mainIndex;
for (register unsigned short k = 1; k <= subArrLen-1; k++, l++) // one bubble sort iteration through the current sub array of the outer loop
{
if (mainArray[l] > mainArray[l+1])
{
swapSort(&mainArray[l], &mainArray[l+1]);
j++;
}
}
if (j == 0)
{
mainIndex = l; // once a subarray is sorted, we need to set mainindex to l's current value so that it can start on the next subarray the next time bubble sort is invoked
break;
}
}
subArrNo++; // the incrementation is done here so that a final iteration can be done on the loop based on the following if statement
if ((subArrNo > total_number_of_subarrays) && (remSizeSubArr >= 2))
{
subArrLen = remSizeSubArr;
mainIndex++;
goto BubbleSort;
}
}
sizeSubArr *= 2; // the incrementation is done here so that a final iteration can be done on the loop based on the following if statement
if (sizeSubArr > n && remSizeSubArr != 0)
{
sizeSubArr = n;
goto SubArrayMarkers;
}
}
}
我尝试了什么：
我已经调试，调试和调试过。我已经将问题精确定位到l变量但似乎无法理解为什么即使对于10个整数数组它也会膨胀到100+值。在任何情况下都不应该超过10。
What I have tried:
I have debugged and debugged and debugged. I have pinpointed the problem to the l variable but can't seem to see why it's inflating to 100+ value even for a 10 integer array. It's not supposed to go beyond 10, in any case.
推荐答案
这里的错误：
Bug here:
int arrayInput[n];
只要 n 在编译时已知。在您的情况下，您需要在运行时使用指针和动态内存分配。
C库函数 - malloc（） [ ^ ]
错误：
This is ok as long as n is known at compile time. In your case, you need to resort to pointer and dynamic memory allocation at runtime.
C library function - malloc()[^]
Bug again:
void mergeSort (int mainArray[])
你不能将数组作为参数传输，参数必须是一个指向数组的指针。
这是一个很好的讲座：
C编程语言 - 维基百科，免费的百科全书 [ ^ ]
https://hassanolity.files.wordpress.com/2013/11/the_c_programming_language_2.pdf [ ^ ]
http://www.ime.usp.br/~pf/Kernighan-Ritchie/C-Programming-Ebook.pdf [ ^ ]
[更新]
- 泡泡排序已经到位，因为它只是通过交换来执行排序。
- 快速排序和合并排序都需要求助于数组副本，因为合并部分不能就地完成（或者它需要特殊的编程来合并到位）。
带链接列表，你可以避免复制数据，因为一切都是通过更改指针来完成的，但是它需要付出代价。
you can't transmit an array as parameter, the parameter must be a pointer to the array.
Here is a good lecture:
The C Programming Language - Wikipedia, the free encyclopedia[^]
https://hassanolity.files.wordpress.com/2013/11/the_c_programming_language_2.pdf[^]
http://www.ime.usp.br/~pf/Kernighan-Ritchie/C-Programming-Ebook.pdf[^]
[Update]
- Bubble sort is done in place because it only resort swaping to perform the sort.
- Quick sort and Merge sort both need to resort to array copy because the merge part can't be done in place (or it need special programming to merge in place).
With linked list, you can avoid copying data because everything is done by changing pointers, but it comes at cost.
好的... s所有。我找到了解决方案。这是一个if语句，搞砸了事情。无论如何，这里是导致问题的if语句的更新代码：
Okay ... sorry, all. I found the solution. It was an if statement that was screwing things up. Anyway, here is the updated code of the if statement that was causing the problem:
if ((subArrNo > total_number_of_subarrays) && (remSizeSubArr >= 2))
{
if (remSwaps != 0)
break;
subArrLen = remSizeSubArr;
mainIndex++;
remSwaps++;
goto BubbleSort;
}
这篇关于在没有数组崩溃的情况下合并排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
