为什么程序在数组中的109个元素之后被卡住了？

Question

这是快速排序的代码。生成的数组是随机的，使用随机()函数，上限为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”，用于在每次解析后打印数组。

我想知道错误的原因，以及如何对大小> 10,000的数组进行排序。

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

1. 不使用VLA。malloc it，这样您就可以在没有堆栈溢出风险的情况下增长。

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;

现在这个程序就终止了。