c - 改变C中数组的大小

Question

我编写了一个生成随机数组并使用插入和快速排序算法对其进行排序的程序。该程序还测量每个函数的运行时间。数组的大小在序言中定义为参数化宏 L。我的问题是:

How can I test both sorting algorithms with arrays of various sizes in a single execution?

我希望我的程序在一次执行中对大小为 L=10, 100, 1000, 5000 和 10000 的数组进行排序。我的程序代码详细如下。

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

//Random Array Length
#define MAX 100
#define L 10

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

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

    //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];

    //Unsorted Array
    printf("\nUnsorted array:   ");
    for(i=0; i<L; i++)
            printf("%d    ", a[i]);

    //Insertion Sort (1e)
    tic = clock();
    naive_sort(a);
    printf("\nInsertion Sort:   ");
            for(i=0; i<L; i++)
                printf("%d    ", a[i]);
    toc = clock();
    printf("  (Runtime: %f seconds)\n", (double)(toc-tic)/CLOCKS_PER_SEC);

    //Quicksort (1f)
    tic = clock();
    smarter_sort(b,0,L-1);
    printf("Quicksort:        ");
            for(i=0; i<L; i++)
                printf("%d    ", b[i]);
    toc = clock();
   printf("  (Runtime: %f seconds)\n", (double)(toc-tic)/CLOCKS_PER_SEC);

   return 0;
}

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

如有任何反馈，我将不胜感激。

---

编辑: 我按照建议修改了代码，它适用于较小的值。但是对于快速排序的情况 L=100 及以后，我没有得到任何输出:

如您所见，我得到的少数输出为零。代码有什么问题？

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

//Random Array Length
#define MAX 100

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((t < a[j]) && (j >= 0)){
            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

我会在每个函数中以参数形式给出数组的长度，并确保您不会尝试访问数组之外​​的元素，例如交换将变为:

int swap(int *a, int length, int i, int j)
{
    if(i>=length || j>=length)
        return -1;
    int t=a[i];
    a[i]=a[j];
    a[j]=t;
    return 0;
}

另请注意返回 -1 或 0 以指示失败。将其应用于其余代码，您将拥有可应用于任何数组的内容。