C语言 为什么程序在数组中有109个元素后卡住?

Question

这是快速排序的代码。使用random()函数生成的数组是随机的，上限为10,000。

当元素数超过109(例如110)时，程序未完成执行而卡住.

这是代码:

/*
Program to sort a list of numbers using Quick sort algorithm.
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// For runtime calculation
#define BILLION 1000000000
// For random number upper limit
#define UPPER_LIMIT 10000
// For printing array
#define PRINT_ARR printf("Parse %d: ", parseCount); for (int p = 0; p < eltCount; p++) printf("%d ", *(ptrMainArr + p)); printf("n"); parseCount++;
// Declare global parse counter
int parseCount = 0;
// Declare global pointer to array
int *ptrMainArr;
// Number of elements in array
int eltCount;
float calcRunTime(struct timespec start, struct timespec end) {
long double runTime;

if (end.tv_nsec - start.tv_nsec >= 0) {
runTime = (end.tv_sec - start.tv_sec) + ((float)(end.tv_nsec - start.tv_nsec) / BILLION);
}
else {
runTime = (end.tv_sec - start.tv_sec - 1 + ((float)(end.tv_nsec - start.tv_nsec) / BILLION));
}

return runTime;
}
void swap(int *ptr1, int *ptr2) {
int temp = *ptr1;
*ptr1 = *ptr2;
*ptr2 = temp;
}
void quicksort(int *ptrArr, int numOfElts) {
// Single element in sub-array
if (numOfElts == 1) {
return;
}

// No elements in sub-array
if (numOfElts == 0) {
return;
}

// Print elements in array
PRINT_ARR

// Select pivot element (element in middle)
int pivotIdx;

// Even number of elements in array
if ((numOfElts) % 2 == 0) {
pivotIdx = ((numOfElts) / 2) - 1;
}
// Odd number of elements in array
else {
pivotIdx = (int)((numOfElts) / 2);
}

int pivot = *(ptrArr + pivotIdx);

// Initialise left and right bounds
int lb = 0, rb = numOfElts - 2;

// Swap pivot element with last element
swap(ptrArr + pivotIdx, ptrArr + numOfElts - 1);

while (1) {
while (*(ptrArr + lb) < pivot) {
lb++;
}
while (*(ptrArr + rb) > pivot && lb <= rb) {
rb--;
}
if (lb > rb) {
break;
}
swap(ptrArr + lb, ptrArr + rb);
}

swap(ptrArr + lb, ptrArr + (numOfElts - 1));

// Sort left sub-array
quicksort(ptrArr, lb);

// Sort right sub-array
quicksort(ptrArr + (lb + 1), numOfElts - lb - 1);
}
int main() {
printf("*** Quick Sort *** n");
printf("Enter number of elements: ");
scanf("%d", &eltCount);

int arr[eltCount];
for (int i = 0; i < eltCount; i++) {
arr[i] = random() % UPPER_LIMIT + 1;
}

// Assign array to global pointer variable (to print array after each parse)
ptrMainArr = arr;
// Note: arr -> Pointer to array's first element

// Start clock
struct timespec start, end;
clock_gettime(CLOCK_REALTIME, &start);

// Sort array using quicksort
quicksort(arr, eltCount);

// End clock
clock_gettime(CLOCK_REALTIME, &end);

printf("Quick sort time taken is %f s.n", calcRunTime(start, end));

return 0;
}

对于110以下的值，我运行了这段代码，并且代码正常工作。包含一个宏函数'PRINT_ARR'，用于在每次解析后打印数组。

我想知道错误的原因，以及如何排序大小为>10000 .

Answer 1

对于任意一对相等的数字，分划函数都失败。它可以通过添加=来固定。此外，交换后可以增加lb和减少rb:

while (1) {
while (*(ptrArr + lb) < pivot) {
lb++;
}
while (*(ptrArr + rb) > pivot && lb <= rb) {
rb--;
}
if (lb >= rb) { // <--------------------------------------------------
break;
}
swap(ptrArr + lb++, ptrArr + rb--); // <------------------------------
}

附加建议:

1. 删除控制台输入，使用固定号码进行测试。
2. 你的calcRunTime函数坏了。只要使用你的第一个方程:

long double calcRunTime(struct timespec start, struct timespec end) {
return (end.tv_sec - start.tv_sec) + ((float)(end.tv_nsec - start.tv_nsec) / BILLION);
}

3. 不要使用VLA。malloc它，所以你可以在没有堆栈溢出风险的情况下增长。

Answer 2

首先，我通过编译程序并使用109(ok)和110(不终止)运行它来重现该问题。然后我将eltCount硬编码为110，因此程序不再需要交互式输入。删除不相关的功能。修改了PRINT_ARR以接受数组和len。在排序之前打印数组，特别注意最后一个元素:

#define PRINT_ARR(arr, len) for (unsigned i = 0; i < (len); i++) printf("%d ", arr[i]); printf("n")
int main() {
unsigned eltCount = 110;
int arr[eltCount];
for (unsigned i = 0; i < eltCount; i++) {
arr[i] = random() % UPPER_LIMIT + 1;
}
PRINT_ARR(arr, eltCount);
quicksort(arr, eltCount);
PRINT_ARR(arr, eltCount);
return 0;
}

,发现:

9384 887 2778 6916 7794 8336 5387 493 6650 1422 2363 28 8691 60 7764 3927 541 3427 9173 5737 5212 5369 2568 6430 5783 1531 2863 5124 4068 3136 3930 9803 4023 3059 3070 8168 1394 8457 5012 8043 6230 7374 4422 4920 3785 8538 5199 4325 8316 4371 6414 3527 6092 8981 9957 1874 6863 9171 6997 7282 2306 926 7085 6328 337 6506 847 1730 1314 5858 6125 3896 9583 546 8815 3368 5435 365 4044 3751 1088 6809 7277 7179 5789 3585 5404 2652 2755 2400 9933 5061 9677 3369 7740 13 6227 8587 8095 7540 796 571 1435 379 7468 6602 98 2903 3318 493 

最后一个数字没有什么特别的，只是上面提到的@RetiredNinja是重复的。

由于问题是一个无限循环，我查看了循环并指定了它们的退出条件。根据上面的提示，我将其更改为仅在两个边界相等时才存在:

if(lb >= rb) break;

，程序终止。