我编写了一个生成随机数组的程序,并使用insert和quicksort算法对其进行排序。 该程序还测量每个函数的运行时间。 arrays的大小在前导码中定义为参数化宏L
我的问题是:
如何在一次执行中使用各种大小的数组测试两种排序算法?
我希望我的程序在一次执行中对大小为L=10, 100, 1000, 5000
和10000
数组进行排序。 我的程序代码详述如下。
#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 secondsn", (double)(toc-tic)/CLOCKS_PER_SEC); //Quicksort (1f) tic = clock(); smarter_sort(b,0,L-1); toc = clock(); printf("Quicksort Runtime: %f secondsn", (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的内容。
以上就是c/c++开发分享改变C中数组的大小相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注计算机技术网(www.ctvol.com)!)。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/549712.html