|
|
#pragma once
|
|
|
#include <stdio.h>
|
|
|
#include <stdlib.h>
|
|
|
#include <string.h>
|
|
|
#include <time.h>
|
|
|
#include <windows.h>
|
|
|
|
|
|
#include "YourPartition.h"
|
|
|
|
|
|
|
|
|
#define MAXN 600//设置数组最大长度
|
|
|
|
|
|
/**
|
|
|
* 统计partitionAlg排序算法对大小从incN，2*incN,3*incN,...,到maxN的数组进行排序的时间
|
|
|
* 对不同大小的数组分别测试numTrials次，记录总的时间
|
|
|
*/
|
|
|
void timePartition(FILE *fp,
|
|
|
int incN,
|
|
|
int maxN,
|
|
|
int numTrials)
|
|
|
{
|
|
|
void printUsage();//函数声明
|
|
|
int (*p)[MAXN];
|
|
|
double start_time=0,end_time=0;
|
|
|
|
|
|
|
|
|
LARGE_INTEGER startCount;
|
|
|
LARGE_INTEGER endCount;
|
|
|
LARGE_INTEGER freq;
|
|
|
double elapsed;
|
|
|
if (QueryPerformanceFrequency(&freq) == 0)//作用：返回硬件支持的高精度计数器的频率。返回值：非零，硬件支持高精度计数器；零，硬件不支持，读取失败。
|
|
|
{
|
|
|
// 硬件不支持高精度计数器
|
|
|
throw "硬件不支持高精度计数器!";
|
|
|
}
|
|
|
|
|
|
for (int n = incN; n <= maxN; n += incN)
|
|
|
{
|
|
|
srand( time(NULL) );
|
|
|
printf( "timing n == %d ",n );
|
|
|
//产生numTrials+1个大小为600的二维随机数组p
|
|
|
p = (int (*)[MAXN])malloc((numTrials + 1)*MAXN*sizeof(int));
|
|
|
|
|
|
for (int t = 0; t < numTrials + 1; t++)
|
|
|
{
|
|
|
for (int x = 0 ; x < n ; x++)
|
|
|
p[t][x]=rand();
|
|
|
}
|
|
|
|
|
|
int movenum = 0;
|
|
|
int compnum = 0;
|
|
|
int bytesnum = 0;
|
|
|
|
|
|
Partition(p[numTrials], n, movenum, compnum, bytesnum); // 对p[numTrials]排序不统计运行时间
|
|
|
// 开始计时器
|
|
|
QueryPerformanceFrequency(&freq);
|
|
|
QueryPerformanceCounter(&startCount);// 对p[0]..p[numTrials-1]共numTrials个大小为n的一维随机数组进行排序，统计运行总时间
|
|
|
// 统计划分时间
|
|
|
for (int t = 0; t < numTrials; t++)
|
|
|
{
|
|
|
Partition(p[t], n, movenum, compnum, bytesnum);
|
|
|
}
|
|
|
// 停止计时器
|
|
|
QueryPerformanceCounter(&endCount);
|
|
|
printf(" -Partition \n");
|
|
|
|
|
|
// 返回计时器经过时间(单位：秒)
|
|
|
elapsed = (double)(endCount.QuadPart - startCount.QuadPart) / freq.QuadPart;
|
|
|
fprintf(fp, "算法对大小为 %d 的数组划分 200 次所耗费的总时间为： %f ms ,元素移动总次数： %d , 元素值比较总次数： %d ,辅助空间总字节数： %d \n", n, elapsed * 1000, movenum, compnum, bytesnum);
|
|
|
}
|
|
|
}
|
|
|
|
|
|
// 打印出数组a[]中的所有元素
|
|
|
void printData(int a[],int n)
|
|
|
{
|
|
|
for (int i = 0; i < n - 1; i++)
|
|
|
{
|
|
|
printf("%d ",a[i]);
|
|
|
}
|
|
|
if (n - 1 >= 0)
|
|
|
{
|
|
|
printf("%d",a[n - 1]);
|
|
|
}
|
|
|
}
|
|
|
/** 打印一个正确调用主函数的参数说明 */
|
|
|
void printUsage()
|
|
|
{
|
|
|
printf("Usage:");
|
|
|
printf(" PartitionPerf <incr> <max> <runs> <outfile>");
|
|
|
printf(" incr - the initial array size and increment");
|
|
|
printf(" max - the maximum array size");
|
|
|
printf(" runs - the number of runs for each size");
|
|
|
printf(" outfile - is the name of the timing output file");
|
|
|
}
|
