c - 为什么我的程序不能用于大型数组？

Question

我发布了 this早些时候在网站上提出的问题，我设法(或多或少)找到了谁的解决方案。简而言之，我需要针对各种大小的数组测试插入和快速排序算法，并查看它们的运行时间如何随数组大小而变化。

唯一的问题是，当我的程序试图为包含 100 个或更大元素的数组计算快速排序算法的运行时时，它似乎停止了。我试过调试代码，但我似乎无法理解为什么会这样。当我运行它时，这是我得到的输出:

为什么停在那里？为什么运行时间为零？谁能帮我这个？在我原来的问题中，一些评论者建议我使用 malloc 但我不确定如何去做。

下面列出了我的代码，如有任何建议，我将不胜感激。

/*
 * Task 1, question h
 */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

//Random Array Length
#define MAX 1000

void perf_routine(int);
void naive_sort(int[],int);
void smarter_sort(int[],int,int);
void swap(int[],int,int);
int choose_piv(int[],int,int);

int main(){
    perf_routine(10);
    perf_routine(100);
    perf_routine(1000);
    perf_routine(5000);
    perf_routine(10000);
   return 0;
}

void perf_routine(int L){
    int i, a[L], b[L];
        clock_t tic, toc;

        printf("Arrays of Length %d:\n", L);

        //Generate an array of random numbers
        for(i=0; i<L; i++)
            a[i]= rand() % (MAX+1);

        //Define b identical to a for fair comparison
        for(i=0; i<L; i++)
            b[i]=a[i];

        //Insertion Sort (1e)
        tic = clock();
        naive_sort(a, L);
        toc = clock();
        printf("Insertion Sort Runtime: %f seconds\n", (double)(toc-tic)/CLOCKS_PER_SEC);

        //Quicksort (1f)
        tic = clock();
        smarter_sort(b,0,L-1);
        toc = clock();
       printf("Quicksort Runtime: %f seconds\n", (double)(toc-tic)/CLOCKS_PER_SEC);
}

void naive_sort(int a[], int L){
    int i, j, t;
    for(i=1; i < L; i++){
        t=a[i];
        j=i-1;
        while((j >= 0) && (t < a[j])){
            a[j+1] = a[j];
            j--;
        }
        a[j+1]=t;
    }
}

void smarter_sort(int a[], int l, int r){
    if(r > l){
        int piv = choose_piv(a, l, r);
        smarter_sort(a, l, piv-1);
        smarter_sort(a, piv+1, r);
    }
}

void swap(int a[], int i, int j){
    int t=a[i];
    a[i]=a[j];
    a[j]=t;
}

int choose_piv(int a[], int l, int r){
    int pL = l, pR = r;
    int piv = l;
    while (pL < pR){
        while(a[pL] < a[piv])
            pL++;
        while(a[pR] > a[piv])
            pR--;
        if(pL < pR)
            swap(a, pL, pR);
    }
    swap(a, piv, pR);
    return pR;
}

Answer 1

如果数组中有重复值，

choose_piv 会进入无限循环。如果a[pL]、a[pR]和a[piv]相同，则内部while code> 循环都立即退出，swap 没有效果(因为两个值相同)，外层 while 循环将永远循环下去。尝试使用所有元素都相同(例如，全为零)的小数组。