c - 为什么在将反向排序数组作为输入时出现段错误？

Question

我正在针对各种分布测试它，当将反向(降序)排序的数组作为输入给出时，我会遇到段错误。有时它甚至对于反向排序数组也能很好地工作，有时我会遇到段错误，特别是在大型反向排序数组(> 100000)上。是不是因为递归调用很深如果是那么递归调用深度的极限是多少，它取决于什么因素以及在编写递归程序时需要注意哪些预防措施。

int partation(double *a, int lower, int upper) {
    int i = lower, j = upper;
    double t = a[lower], temp;
    while (i <= j) {
        while (i <= upper && a[i] <= t)
            i++;
        while (a[j] > t)
            j--;
        if (i <= j) {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }
    temp = a[lower];
    a[lower] = a[j];
    a[j] = temp;
    return j;
}

void quick_sort(double *a, int lower, int upper) {
    int j;
    if (lower >= upper)
        return;
    else {
        j = partation(a, lower, upper);
        quick_sort(a, lower, j - 1);
        quick_sort(a, j + 1, upper);
    }
}

Answer 1

由于堆栈溢出，您遇到了段错误。

反向排序的数组是您的分区方案的最坏情况:您对 n 元素的数组递归 n-1 次。

您可以尝试改进分区方案以避免这种病态情况，但是在 quick_sort 函数中有一种方法可以避免深度递归:在较小的一半上递归，在较大的一半上循环.病理情况只会很慢但不会再崩溃。

代码如下:

#include <stdio.h>
#include <time.h>

int partition(double *a, int lower, int upper) {
    /* assuming lower < upper */
    int i = lower, j = upper;
    double t = a[lower], temp;
    while (i <= j) {
        while (i <= upper && a[i] <= t)
            i++;
        while (a[j] > t)
            j--;
        if (i < j) {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }
    temp = a[lower];
    a[lower] = a[j];
    a[j] = temp;
    return j;
}

void quick_sort(double *a, int lower, int upper) {
    while (lower < upper) {
        int j = partition(a, lower, upper);
        if (j - lower < upper - j) {
            if (lower < j - 1) {
                quick_sort(a, lower, j - 1);
            }
            lower = j + 1;
        } else {
            if (j + 1 < upper) {
                quick_sort(a, j + 1, upper);
            }
            upper = j - 1;
        }
    }
}

int main(void) {
    double a[65536];
    for (int n = 2; n <= (int)(sizeof(a) / sizeof(*a)); n += n) {
        for (int i = 0; i < n; i++) {
            a[i] = n - i;
        }
        clock_t t = clock();
        quick_sort(a, 0, n - 1);
        t = clock() - t;
        for (int i = 1; i < n; i++) {
            if (a[i - 1] > a[i]) {
                printf("out of order at %d: %f > %f\n", i - 1, a[i - 1], a[i]);
                return 1;
            }
        }
        printf("a[%d] sorted in %.3f msec\n", n, (double)t * 1000.0 / CLOCKS_PER_SEC);
    }
    return 0;
}

输出:

a[2] sorted in 0.002 msec
a[4] sorted in 0.001 msec
a[8] sorted in 0.001 msec
a[16] sorted in 0.001 msec
a[32] sorted in 0.000 msec
a[64] sorted in 0.002 msec
a[128] sorted in 0.006 msec
a[256] sorted in 0.021 msec
a[512] sorted in 0.074 msec
a[1024] sorted in 0.287 msec
a[2048] sorted in 1.185 msec
a[4096] sorted in 5.104 msec
a[8192] sorted in 19.497 msec
a[16384] sorted in 78.140 msec
a[32768] sorted in 297.297 msec
a[65536] sorted in 1175.032 msec

关于你的第二个问题，它取决于什么因素，在编写递归程序时需要采取哪些预防措施？没有确定的答案:

• 堆栈空间的限制(如果有这样的概念)是特定于实现的，不同的系统有非常不同的限制:从小型嵌入式系统的几千字节到大型系统的几兆字节。

• 递归数千次是有风险的，定义具有自动存储的大型数组也是如此。在上面的代码中，我定义了一个 64K double 组，这在现代通用计算机上不是问题，但在小型数字传感器上可能太多了。 recurse on smaller half 方法的最大递归级别受 log(N) 限制，对于 N=，它仅为 16 65536，所有系统应该都可以。