quick sort とselection sortの実行時間の計測

[るびーぐらふる]

test.txtから英単語を読み込み、それを辞書式順序に整列するプログラムです。
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]) { //先頭から１文字ずつ比較
                    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);
    }
}

[Bull]

時間の計算がおかしいようですね。

コード:

     msec=timebf.time-msec;

は

コード:

     msec=timebf.millitm-msec;

でしょうか？

[るびーぐらふる]

解決しました！ありがとうございます。