改变C中数组的大小

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

如何在一次执行中使用各种大小的数组测试两种排序算法?

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

 #include  #include  #include  //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 = 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]) pR--; if(pL < pR) swap(a, pL, pR); } swap(a, piv, pR); return pR; } 

我将不胜感激任何反馈。


编辑:我修改了建议的代码,它适用于小值。 但是对于快速排序案例L=100而且超出它,我没有得到任何输出:

在此处输入图像描述

正如你所看到的,我得到的少数输出为零。 代码有什么问题?

 /* * Task 1, question h */ #include  #include  #include  //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 = 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]) pR--; if(pL < pR) swap(a, pL, pR); } swap(a, piv, pR); return pR; } 

当数组传递给函数时,它们作为(或“衰减到”)指针传递给它们的第一个元素。 无法知道arrays的大小。

因此,将实际长度作为附加参数传递给函数是很常见的。 如果下面有一个不同大小的三个数组的天真排序示例。

当然,必须注意保持arrays和长度同步。 传递太大的长度可能会导致未定义的行为。 例如,在下面的示例中调用fill(tiny, LARGE)可能会导致灾难。

(旁白:数组可能具有最大长度或容量和实际长度。例如,如果要从文件中读取最多十个数字,则必须传递长度为10的数组,但如果只读取四个数字,你在这里处理两个额外的参数:可能的数组长度,10和实际长度,4。但这不是这里的情况。)

嗯,这里有。 所有三个数组函数都具有相同的签名:它们采用数组及其长度。

 #include  #include  #include  void sort(int a[], size_t len) { size_t i, j; for (i = 1; i < len; i++) { int t = a[i]; j = i - 1; while (j >= 0 && t < a[j]) { a[j + 1] = a[j]; j--; } a[j + 1] = t; } } void fill(int a[], size_t len) { size_t i; for (i = 0; i < len; i++) { a[i] = rand() / (1.0 + RAND_MAX) * 100; } } void print(int a[], size_t len) { size_t i; for (i = 0; i < len; i++) { if (i) printf(", "); printf("%d", a[i]); } puts(""); } #define TINY 3 #define MEDIUM 10 #define LARGE 15 int main(void) { int tiny[TINY]; int medium[MEDIUM]; int large[LARGE]; srand(time(NULL)); fill(tiny, TINY); fill(medium, MEDIUM); fill(large, LARGE); print(tiny, TINY); print(medium, MEDIUM); print(large, LARGE); sort(tiny, TINY); sort(medium, MEDIUM); sort(large, LARGE); print(tiny, TINY); print(medium, MEDIUM); print(large, LARGE); return 0; } 

我会在每个函数中给出参数中数组的长度,并确保不要尝试到达数组之外的元素,例如swap将变为:

 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表示失败。 将其应用于其余代码,您将拥有可应用于任何arrays的内容。