C语言递归选择排序处理大输入时触发Segmentation Fault求助

问题描述 #

实现了递归版本的选择排序C语言程序，当输入规模达到10000及以上时触发Segmentation Fault（段错误），调试器显示错误发生在findmin递归函数中。小输入规模下程序运行正常，已验证数组生成函数和swap函数的正确性。

inputType枚举用于控制数组元素顺序：

• ORDINATO：有序
• QUASI_ORDINATO：近乎有序
• INV_ORDINATO：逆序
• CASUALE：随机

原代码如下：

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

#define DIM_VEC 6
#define MAX_RAND 100

typedef enum {
    ORDINATO, QUASI_ORDINATO, INV_ORDINATO, CASUALE
} inputType;

//Funzione genera_array(…)
int *generaArray(int dimensione, inputType tipo_schema);

void swap(int *a, int *b);

//E2_1: Selection Sort ricorsivo con interi
void selectionSortRec(int A[], int dimA, int start);
int findmin(int A[], int minpos, int start, int dim);

int main() {
    setvbuf(stdout, NULL, _IONBF, 0);
    int ord, dim;
    int *array = NULL;
    int N[DIM_VEC] = {100, 1000, 10000, 100000, 200000, 500000};
    double tempo;
    srand(time(NULL));

    printf("\nScegli l'ordine dell'array "
           "\n0 - ORDINATO, 1 - QUASI_ORDINATO, 2 - INV_ORDINATO, 3 - CASUALE");
    scanf("%d", &ord);
    if(ord < 0 || ord > 3)
        ord = 0;

    printf("\nScegliere la dimensione dell'array ");
    for(int i = 0; i < DIM_VEC; i++) {
        printf("\n%d -- %d", i, N[i]);
    }
    scanf("%d", &dim);
    if(dim < 0 || dim > 5)
        dim = 0;

    array = generaArray(N[dim], ord);

    tempo = clock();
    selectionSortRec(array, N[dim], 0);
    tempo = (clock() - tempo) / CLOCKS_PER_SEC;
    printf("\nTempo impiegato: %lf", tempo);

    free(array);

    return 0;
}

//Funzione genera_array(…)
int *generaArray(int dimensione, inputType tipo_schema) {
    int *a = calloc(dimensione, sizeof(int));
    int j;

    switch (tipo_schema) {
        case ORDINATO:
            for(int i = 0; i < dimensione; i++)
                a[i] = i;
            break;
        case QUASI_ORDINATO:
            for(int i = 0; i < dimensione / 2; i++) {
                a[i] = i;
            }
            for(int i = dimensione /2; i < dimensione; i++) {
                a[i] = rand() % MAX_RAND;
            }
            break;
        case INV_ORDINATO:
            j = dimensione;
            for(int i = 0; i < dimensione; i++) {
                a[i] = j;
                j--;
            }
            break;
        case CASUALE:
            for(int i = 0; i < dimensione; i++) {
                a[i] = rand() % MAX_RAND;
            }
            break;
    }

    return a;

}

//E2_1: Selection Sort ricorsivo con interi
void selectionSortRec(int A[], int dimA, int start) {
    int minIndex;

    if (start >= dimA - 1)
        return;

    minIndex = findmin(A, start, start +1, dimA);

    swap(&A[minIndex], &A[start]);
    selectionSortRec(A, dimA, start+1);
}
int findmin(int A[], int minpos, int start, int dim) {

    if (start == dim)
        return minpos;

    if (A[start] < A[minpos])
        minpos = start;
    return findmin(A, minpos, start + 1, dim);

}

void swap(int *a, int *b) {
    int aux = *a;
    *a = *b;
    *b = aux;
}

问题根源 #

段错误的核心原因是递归调用栈溢出：

• selectionSortRec的递归深度为O(n)，对n=10000的数组，会产生10000次递归调用
• 每次selectionSortRec调用又会触发findmin的O(n)深度递归，进一步加剧栈空间消耗
• 程序栈的默认大小有限（通常在几MB级别），大量递归调用帧会耗尽栈空间，触发Segmentation Fault

解决方案 #

将递归实现的findmin改为迭代版本，消除这部分递归栈消耗，即可解决大输入下的段错误问题。修改后的findmin函数如下：

int findmin(int A[], int minpos, int start, int dim) {
    for (; start < dim; start++) {
        if (A[start] < A[minpos]) {
            minpos = start;
        }
    }
    return minpos;
}

如果需要进一步优化，也可以将selectionSortRec同样改为迭代实现，彻底避免递归栈的限制：

void selectionSortRec(int A[], int dimA, int start) {
    for (; start < dimA - 1; start++) {
        int minIndex = findmin(A, start, start + 1, dimA);
        swap(&A[minIndex], &A[start]);
    }
}

验证 #

修改后，测试输入规模10000、100000甚至更大的数组，程序均可正常运行，不会再触发段错误。

内容的提问来源于stack exchange，提问作者Giuseppe Guerrini