为什么我的快速排序会在大型反向排序数组中崩溃？

Question

我正在学习 C 并尝试了递归快速排序算法。在小输入尺寸下，它按预期工作；对于随机生成的数组，所有测试大小（最多 100,000）都没有问题。对于降序数组，它以某种方式中断（Windows 给我一条消息，程序已停止工作）在某个数组大小 (32,506)。我的代码中是否有任何错误（例如任何错误的内存分配 - 我不确定我是否做对了）或者 C 在递归调用或其他方面是否有限制？

编辑：我知道我的 Quicksort 实现相当幼稚，并且它对这种输入的表现非常糟糕，但我没想到它会崩溃。

我在 Windows 10 的命令提示符下使用 GCC 和 MinGW。我不确定如何找出到底发生了什么，因为尽管有 [= 我并没有真正收到任何指定的错误消息17=] 告诉我我的程序停止工作了。

#include <stdio.h>
#include <stdlib.h>

int partition(int *a, int lo, int hi) {
    int i = lo; int j = hi+1; int v,t;
    v = a[lo]; //partition element
    while (1) {
        while (a[++i] < v) {if (i == hi) break;}
        while (v < a[--j]) {if (j == lo) break;}
        if (i >= j) break;
        t = a[j]; a[j] = a[i]; a[i]= t; //swap
    }
    t = a[lo]; a[lo] = a[j]; a[j]= t;//swap
    return j;
}

void quicksort(int a[], int lo, int hi) {
    int j;
    if (hi <= lo) return;
    j = partition(a, lo, hi);
    quicksort(a, lo, j-1);
    quicksort(a, j+1, hi);
}

int main()  {
    int len;
    for (len = 32000;len < 40000;len+=100) {
        printf("New Arr with len = %d\n",len);
        int *arr;
        arr = (int*) calloc(len,sizeof(int));
        int j;
        //create descending Array
        for (j = 0; j < len; ++j) {
            arr[j] = len-j;
        }
        printf("start sorting\n");
        quicksort(arr,0,len-1);
        free(arr);
    }
}

Answer 1

递归太深，无法将其存储在堆栈中。它必须为每个级别存储 int j = partition(..)。有一些声明性技术可以最大限度地减少递归堆栈的使用。例如，将结果作为参数。但是这个案例比我举的例子要复杂得多。

Answer 2

对我来说，您的代码在更大的尺寸（约 370,000 个元素）下失败。您可能运行遇到了平台限制（可能由于堆栈溢出而限制了递归深度）。没有确切的错误消息，当然很难确定。

您的输入集可能是您实施的病态案例 - 请参阅 What makes for a bad case for quick sort?

您可以通过更好地选择主元来减少递归深度——一种常用的技术是取第一个、中心和最后一个元素的中值。像这样：

int v0 = a[lo], v1 = a[(lo+hi+1)/2], v2 = a[hi];
/* pivot: median of v0,v1,v2 */
int v = v0 < v1 ? v1 < v2 ? v1 : v0 < v2 ? v2 : v0 : v0 < v2 ? v0 : v1 < v2 ? v2 : v1;

您还可以通过仅递归较小的分区并使用迭代处理较大的分区来减少递归深度。您也许能够让编译器的尾调用消除器将递归转换为迭代，但如果这不起作用，您将需要自己编写。类似于：

void quicksort(int a[], int lo, int hi) {
    while (lo < hi) {
        int j = partition(a, lo, hi);
        if (j - lo < hi -j) {
            quicksort(a, lo, j-1);
            lo = j+1;
        } else {
            quicksort(a, j+1, hi);
            hi = j-1;
        }
    }
}

通过上述更改，我可以对超过 10 亿个元素的数组进行排序而不会崩溃（我必须进行一些性能改进 - 见下文 - 即使那样，也需要 17 秒）。

您可能还想 return 尽早发现子数组已经排序。我会把它留作练习。

P.S。 main():

中的几个问题

您不测试 calloc() 的结果 - 您可能应该改用 malloc()，因为无论如何您都会编写每个元素：

int *arr = malloc(len * sizeof *arr);
if (!arr) return fprintf(stderr, "allocation failed\n"), EXIT_FAILURE;

完整列表

这是我最终得到的代码：

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int partition(int *a, int i, int j) {
    int v0 = a[i], v1 = a[(i+j+1)/2], v2 = a[j];
    /* pivot: median of v0,v1,v2 */
    int v = v0 < v1 ? v1 < v2 ? v1 : v0 < v2 ? v2 : v0 : v0 < v2 ? v0 : v1 < v2 ? v2 : v1;
    while (i < j) {
        while (a[i] < v && ++i < j)
            ;
        while (v < a[j] && i < --j)
            ;
        int t = a[j]; a[j] = a[i]; a[i]= t; //swap
    }
    /* i == j; that's where the pivot belongs */
    a[i] = v;
    return j;
}

void quicksort(int a[], int lo, int hi) {
    while (lo < hi) {
        int j = partition(a, lo, hi);
        if (j - lo < hi -j) {
            quicksort(a, lo, j-1);
            lo = j+1;
        } else {
            quicksort(a, j+1, hi);
            hi = j-1;
        }
    }
}

int main()  {
    int len = INT_MAX/2+1;
    printf("New Arr with len = %d\n",len);
    int *arr = malloc(len * sizeof *arr);
    if (!arr) return fprintf(stderr, "allocation failed\n"), EXIT_FAILURE;

    /* populate pessimal array */
    for (int j = 0; j < len; ++j) {
        arr[j] = len-j;
    }

    printf("start sorting\n");
    quicksort(arr, 0, len-1);

    /* test - is it sorted? */
    for (int i = 0;  i+1 < len;  ++i)
        if (arr[i] >= arr[i+1])
            return fprintf(stderr, "not sorted\n"), EXIT_FAILURE;
    free(arr);
}

为什么我的快速排序会在大型反向排序数组中崩溃？

Why does my quicksort crash with large, reverse-sorted arrays?

c

recursion

quicksort

完整列表