c - 尝试声明 int 数组时数组声明失败

Question

我学习排序算法并编写代码已经有一段时间了，最​​近我用 C 编写了合并排序，并且还编写了一个 sort_test 函数测试我写的函数。在排序测试函数中，我声明一个数组并为其分配随机值，但是当数组大小达到 1,000,000 时，程序崩溃。为什么会发生这种情况？

sort_test.c

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "merge_sort.h"
#include "sort_test.h"

// test size
#define MIN 10
#define MAX 1000000

// int comparator

int cmpInt(const void *elem1,const void * elem2){
    int e1 = *(int *)elem1; // i-1
    int e2 = *(int *)elem2; // i
    if(e2 < e1){
        return -1;
    } else if(e2 > e1){
        return 1;
    } else {
        return 0;
    }
}

// double comparator

int cmpDouble(const void *elem1,const void *elem2){
    double e1 = *(double *)elem1;
    double e2 = *(double *)elem2;
    if(e2 < e1){
        return -1;
    } else if(e2 > e1){
        return 1;
    } else {
        return 0;
    }
}

void initSeed(){
    srand(time(NULL));
}

void intSortTest(){
    initSeed();
    for(size_t i = MIN;i <= MAX;i *=10){
        int arr[i];
        for(size_t j = 0; j < i;j++){
            arr[j] = rand();
        }
        // sorting the array
        mergesort(arr,0,i);
        // checking if sorted array hold the 
        // condition i[0] <= i[1] ... <= i[n].
        for(size_t j = 1;j < i;j++){
            int *e1 = &arr[j-1];
            int *e2 = &arr[j];
        assert(cmpInt(e2,e1) <= 0);
        }
        printf("INT TEST : %7d\tPASSED\n",i);
    }
    printf("\n");
}

void doubleSortTest(){
    initSeed();
    for(int i = MIN; i <= MAX; i *= 10){
        double arr[i];
        for(int j = 0 ; j < i;j++){
            arr[j] = (double)(rand() % 100) + 1.0;
        }
        // perform sort
        //insertion_sort(arr,sizeof (double),i,cmpDouble);
        for(int j = 1; j < i;j++){
            double *e1 = &arr[j-1];
            double *e2 = &arr[j];
            assert(cmpDouble(e2,e1) <= 0);
        }
        printf("Double Test : %5d\tPASSED\n",i);
    }
    printf("\n");
}

sort_test.h

#ifndef SORT_TEST_H
#define SORT_TEST_H

void initSeed();
void intSortTest();
void doubleSortTest();
int cmpDouble(const void *elem1,const void *elem2);
int cmpInt(const void *elem1,const void * elem2);

#endif // SORT_TEST_H

merge_sort.h

#ifndef MERGE_SORT_H
#define MERGE_SORT_H

void mergesort(int *arr,int start,int end);
void merge(int *arr,int start,int med,int end);

#endif // MERGE_SORT_H

merge_sort.c

#include <stdio.h>
#include "sort_test.h"
#include "merge_sort.h"

int main(){
    intSortTest();
    return 0;
}

void mergesort(int *arr,int start,int end){
    if(start < end){
        int median = (end + start) / 2;
        mergesort(arr,start,median);
        mergesort(arr,median+1,end);
        merge(arr,start,median,end);
    }
}

void merge(int *arr,int start,int median,int end){
    int i = start; int j = median+1;
    int copy[end+1];
    int cIndex = 0;

    while(i <= median && j <= end) {
        if(arr[j] <= arr[i]){
            copy[cIndex++] = arr[j++];
        } else {
            copy[cIndex++] = arr[i++];
        }
    }

    while(i <= median){
        copy[cIndex++] = arr[i++];
    }
    while(j <= end){
        copy[cIndex++] = arr[j++];
    }
    for(int k = 0; k < cIndex; k++){
        arr[start++] = copy[k];
    }
}

Answer 1

这是因为您在堆栈上分配数组。请尝试使用以下代码。

void intSortTest(){
    initSeed();
    for(size_t i = MIN;i <= MAX;i *=10){
        int *arr = malloc(i*sizeof(int));  // <-- changed this
        for(size_t j = 0; j < i;j++){
            arr[j] = rand();
        }
        // sorting the array
        mergesort(arr,0,i);
        // checking if sorted array hold the 
        // condition i[0] <= i[1] ... <= i[n].
        for(size_t j = 1;j < i;j++){
            int *e1 = &arr[j-1];
            int *e2 = &arr[j];
            assert(cmpInt(e2,e1) <= 0);
        }
        printf("INT TEST : %7d\tPASSED\n",i);
        free(arr);   // <-- added this
    }
    printf("\n");
}

编辑

合并算法也不正确。更准确地说，您的值列表边界有问题。

定义值列表的开始和结束索引时，值位于 arr[start] 到 arr[end-1] 中，而不是 arr[结束]。值的数量就是end-start。根据此约定，当 start == end 时，您将得到一个空列表。

因此，函数 mergesort 变为:

void mergesort(int *arr,int start,int end){
    if (start+1 >= end) 
        return; // a list with 0 or 1 values is already sorted
    int median = (end + start) / 2;
    mergesort(arr,start,median);
    mergesort(arr,median,end);
    merge(arr,start,median,end);
}

合并函数变为如下:

void merge(int *arr,int start,int median,int end){
    int i = start; int j = median;
    int *copy = malloc((end-start)*sizeof(int)); // use malloc for huge arrays
    int cIndex = 0;

    while(i < median && j < end) {  // not i <= median && j <= end
        if(arr[j] <= arr[i]){
            copy[cIndex++] = arr[j++];
        } else {
            copy[cIndex++] = arr[i++];
        }
    }

    while(i < median){ // not i <= median
        copy[cIndex++] = arr[i++];
    }
    while(j < end){  // not j <= median
        copy[cIndex++] = arr[j++];
    }
    for(int k = 0; k < cIndex; k++){
        arr[start++] = copy[k];
    }
    free(copy);
}

如您所见，只有细微的差别。

使用此代码，您的程序运行不会出现错误。