为什么该程序在数组中的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'，用于在每个分析后打印数组。

我想知道错误的原因，以及如何对大小和gt的数组进行排序; 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);
}

3. 不要使用VLA。 malloc它，因此您可以不冒险溢出而生长。

Answer 2

首先，我通过编译您的程序并使用109（OK）和110（未终止）来重现问题。然后，我硬编码eltcount to 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;

该程序现在终止。