clock() 函数不测量 qsort() 时间

Question

我正在尝试编写一个程序，从 CSV 文件中获取一些歌曲数据（~1000 行）并将其放入结构数组中。该 CSV 文件的每一行包含：title of the song、artist 和 release year。字符串、字符串和整数。

取出数据没有问题

这些行正确地写在我的结构数组中（称为 s），而且 bubblesort 部分工作正常。计算冒泡排序的执行时间也有效。我把那段时间写在了回忆里。

之后我正在重置数组，数据再次插入到数组结构中。我正在使用 qsort() 对数组进行排序。该函数执行其预期的操作。该数组的排序方式与按 bubblesort 排序的方式相同。问题是，测量的时间是 0,000....

这是我的 bubblesortTime() 函数，returns 冒泡排序所需的执行时间...排序：

float bubbleSortTime(song *s, int length) {
    int flag;
    song aux;

    clock_t start, end;

    start = clock();

    do {
        flag = 0;
        for (int j = 0; j<length-1; j++) {
            if (s[j].release_year > s[j+1].release_year) {
                aux = s[j];
                s[j] = s[j+1];
                s[j+1] = aux;
                flag = 1;
            }
        }
    } while (flag == 1);

    end = clock();

    clock_t time = end-start;
    float finTime = (float)time/CLOCKS_PER_SEC;


    return finTime;
}

此外，这是我的 qsortTime() 函数，还有 comp():

int comp (const void * a, const void * b)
{
    song *s1 = (song *)a;
    song *s2 = (song *)b;

    return (s1->release_year - s2->release_year);
}

float qsortTime(song *s, int length) {

    clock_t start, end;

    start = clock();

    qsort(s, length, sizeof(s[0]), comp);

    end = clock();

    clock_t time = end-start;
    float finTime = (float)time/CLOCKS_PER_SEC;

    return finTime;
}

显示main()中的两个返回值时，使用：

float time1 = bubbleSortTime(s, i);

/** 
reset code and more things here
**/

float time2 = qsortTime(s, i);
printf("%f %f", time1, time2);

(...) 输出是：0.062500 0.000000，说明 bubblesort 调用的时间计算正确，而 qsort 调用的时间计算不正确't.

我知道 qsort 通常比 bubblesort 慢，这就是我感到困惑的原因。

如果您需要我提供更多代码，请发表评论，我会做的。非常感谢！

Answer 1

使用更大的 N。

首先尝试用较大的 N 只 qsortTime() 进行锻炼。

N = 100,000 且报告时间为“0.062500 0.000000”和 O(n*n) vs O(n*log n)，两种算法之间的时间差可能超过 1000 倍.

对我来说，N = 100,000

Bubble: 47.125
QTSort: 0.016

此外，请确保“重置代码和此处的更多内容”包括给 qsortTime(s, i); 一个未排序的列表，而不是按 bubbleSortTime().

排序的列表

例子

#define SS (100000 * 2)
song s[SS];

int main() {
  // for (int i = 0; i < SS; i++)
  //  s[i].release_year = rand() % 1000;
  // printf("Bubble: %g\n", bubbleSortTime(s, SS));
  for (int i = 0; i < SS; i++)
    s[i].release_year = rand() % 1000;
  printf("QTSort: %g\n", qsortTime(s, SS));
}

clock() 函数不测量 qsort() 时间

clock() function doesn't measure qsort() time

c

clock

qsort

time.h

time-t