quick sortとselection sortの実行時間を比較しようと、計測を試みたところ、サンプル数を増やしても、整列方法を変えても実行時間が変わりません。整列自体はできているようです。
どのようにすれば二つの性能比較ができるか、ご教授願います。
test.txtの中身は"The Gift Of The Magi"で試しました。
#include <stdio.h>
#include <string.h>
#include <sys/timeb.h>
#include <ctype.h>
#include <time.h>
#define MAX 100000
void selectionsort(char *word[], int n);
void quicksort(int left,int right,char *word[]);
void swap_str(char **x, char **y)
{
char *tmp = *x;
*x = *y;
*y = tmp;
}
void swap(int *a,int *b)
{
int t;
t=*a;
*a=*b;
*b=t;
}
int main(void)
{
//計測
double dtime;
int sec,msec;
struct timeb timebf;
//ファイル読み込み
FILE *fp;
char *fname="test.txt";
char s[MAX];
char *s1[MAX]; //単語を格納
int i;
fp=fopen(fname,"r");
if(fp==NULL){
printf("%sファイルが開けません\n",fname);
return -1;
}
printf("--test.txt--\n");
fgets(s,MAX,fp);
printf("%s",s);
printf("\n");
fclose(fp);
//文字列を小文字変換
for(i=0;i<MAX;i++)
s[i]=tolower(s[i]);
//単語に分解
printf("--words--\n");
char s2[] = " .,\"-0123456789$\n{}'?"; /* 空白+カンマ+ピリオド */
char *tok;
i=1;
int j;
tok = strtok( s, s2 );
while( tok != NULL ){
s1[i]=tok;
printf("word[%d]:%s\n",i,s1[i]);
tok = strtok( NULL, s2 ); /* 2回目以降 */
i++;
}
i--;
printf("--word count--\n");
printf("word count:%d\n",i);
//quicksort
printf("--quicksort--\n");
//計測開始
ftime(&timebf);
sec=timebf.time;
msec=timebf.millitm;
quicksort(1,i,s1);
//計測終了
ftime(&timebf);
sec=timebf.time-sec;
msec=timebf.time-msec;
msec+=sec*1000;
etime=(double)msec/1000;
printf("実行時間は%f秒です\n",etime);
for(j=1; j<=i; j++)
printf("word[%d]:%s\n", j, s1[j]);
return 0;
}
void selectionsort(char *word[], int n)
{
int i,j,k,minpos;
char a[20], b[20];
for(i=1; i<=n-1; i++){
minpos = i;
for(j=i+1; j<=n; j++) {
for(k=0; k<20; k++) {
a[k] = *(word[j]+k);
//printf("a[%d]:%c\n",k,a[k]);
b[k] = *(word[minpos]+k);
//printf("b[%d]:%c\n",k,b[k]);
if (a[k] < b[k]) { //先頭から1文字ずつ比較
minpos = j;
break;
}else if(a[k] == b[k]) {
continue;
}else{
break;
}
}
}
swap_str(&word[i],&word[minpos]);
}
}
void quicksort(int left,int right,char *word[])
{
int i,j;
char *pivot=word[(left+right)/2];
if(left<right)
{
i=left;
j=right;
while(i<=j)
{
while(strcmp(word[i],pivot)<0)
i++;
while(strcmp(word[j],pivot)>0)
j--;
if(i<=j)
{
swap_str(&word[i],&word[j]);
i++;
j--;
}
}
quicksort(left,j,word);
quicksort(i,right,word);
}
}