无法从快速排序算法中获取处理时间

Question

我一直在尝试通过 clock_t start, end;

获取排序算法的处理时间

但是控制台没有任何输出。我遇到这堵砖墙已经有一段时间了，需要帮助。

有问题的程序

// TQuicksort.c//
#include <stdio.h>
#include <time.h>

#define NUM 10000  //データ数
#define REPEAT 100000000  //繰り返し数

int quicksort(int a[], int first, int last) {
    int i, j, temp, x;
    
    i = first;
    j = last;
    x = (a[i] + a[j]) / 2;   //基準値は平均
    
    while (1) {
        while (a[i] < x)
            i++;
        while (a[j] > x)
            j--;
        // iがjより大きくなればwhile loopが解除される
        if (i >= j)
            break;
        //a[i]とa[j]を入れ替える
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
        i++;
        j--;
    }
    if (first < i - 1)
        quicksort(a, first, i - 1);
    if (j + 1 < last)
        quicksort(a, j + 1, last);
    return 0;
}

int main(void) {
    int i, n = 0;
    int a[NUM];   //配列
    
    clock_t start, end;   //clock_t型変数
    
    start = clock();   //計測開始時刻を得る
    quicksort(a, 0, NUM - 1);   //クイックソートの呼び出し
    for (i = 0; i < REPEAT; i++)  //繰り返し
        n += i * i * i * i * i;   //ダミー処理
    end = clock();   //計測終了時刻を得る
    printf("time = %.30f sec\n", ((double)end - start) / CLOCKS_PER_SEC);  //処理時間の出力
    return 0;
}

有人可以告诉我我做错了什么吗？

编辑：笨蛋我忘记添加有序数组了。所以， int [NUM];现在是 int a[NUM]={1,2,3,4,5,6,7,8,9]；新问题，更改 NUM 不会更改处理时间。我该怎么做才能解决这个问题？

Answer 1

您的代码中存在多个问题：

x = (a[i] + a[j]) / 2; 可能溢出，具有未定义的行为，并产生一个不在 a[i] 和 a[j] 之间的值，可能导致无限递归。
int a[NUM];未初始化
REPEAT 循环产生一个 n 的值，计算可能会溢出并且不被使用，代码可能被优化编译器删除。

您必须小心计算中点，不要溢出。如果类型 long long 大于 int，则可以使用：

    int x = ((long long)a[i] + a[j]) / 2;

这是修改后的版本，对各种发行版进行了基准测试：

//TQuicksort.c//
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define NUM 100000

void quicksort(int a[], int first, int last) {
    if (first < last) {
        int i = first;
        int j = last;
        int x = ((long long)a[i] + a[j]) / 2;
        int temp;

        for (;;) {
            while (a[i] < x)
                i++;
            while (a[j] > x)
                j--;
            if (i >= j)
                break;
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            i++;
            j--;
        }
        quicksort(a, first, i - 1);
        quicksort(a, j + 1, last);
    }
}

int min(int a, int b) {
    return a < b ? a : b;
}

clock_t test(const char *s, int *a, int len) {
    clock_t c = clock();
    quicksort(a, 0, len - 1);
    c = clock() - c;
    for (int i = 1; i < len; i++) {
        if (a[i] < a[i - 1]) {
            printf("%s: failed\n", s);
            break;
        }
    }
    return c;
}

int main(int argc, char *argv[]) {
    int max = argc > 1 ? strtoul(argv[1], NULL, 0) : NUM;
    int *a = malloc(sizeof(*a) * max);
    const char *name[] = { "rand", "bytes", "bits", "zero", "incr", "decr", "hat" };
    clock_t c[10][7];
    int i, j, k, len;

    for (k = 0, len = max; len >= 10; len /= 10, k++) {
        for (i = 0; i < len; i++) a[i] = rand();       // random ints
        c[k][0] = test(name[0], a, len);
        for (i = 0; i < len; i++) a[i] = rand() & 255; // random bytes
        c[k][1] = test(name[1], a, len);
        for (i = 0; i < len; i++) a[i] = rand() & 1;   // random bits
        c[k][2] = test(name[2], a, len);
        for (i = 0; i < len; i++) a[i] = 0;            // all zeroes
        c[k][3] = test(name[3], a, len);
        for (i = 0; i < len; i++) a[i] = i;            // monotonic increase
        c[k][4] = test(name[4], a, len);
        for (i = 0; i < len; i++) a[i] = -i;           // monotonic decrease
        c[k][5] = test(name[5], a, len);
        for (i = 0; i < len; i++) a[i] = min(i, len - i - 1); // hat shape
        c[k][6] = test(name[6], a, len);
    }
    printf("%10s", "length");
    for (i = 0; i < 7; i++)
        printf("%9s ", name[i]);
    printf("\n");
    for (j = 0, len = max; j < k; j++, len /= 10) {
        printf("%10d", len);
        for (i = 0; i < 7; i++)
            printf(" %9.3f", c[j][i] * 1000.0 / CLOCKS_PER_SEC);
        printf("\n");
    }
    return 0;
}

100000000 的输出：

    length     rand     bytes      bits      zero      incr      decr       hat
 100000000 11073.979  5026.436  2948.862  2456.532  1431.838  1487.996  6790.571
  10000000   971.453   467.954   260.339   239.740   128.600   135.692   573.682
   1000000    86.910    46.189    36.059    31.516    14.522    13.370    57.162
    100000     7.578     4.350     2.529     2.301     1.002     1.510     4.835
     10000     0.748     0.524     0.190     0.145     0.076     0.106     0.502
      1000     0.066     0.055     0.027     0.018     0.013     0.012     0.045
       100     0.007     0.007     0.004     0.002     0.003     0.002     0.004
        10     0.001     0.001     0.000     0.000     0.001     0.002     0.001

如您所见，时间因数字分布而异。在扫描循环中导致最多错误预测的随机分布，因此比具有大量重复项的随机分布要慢，而排序数组甚至更快，因为比较被很好地预测并且发生的交换更少。

时间复杂度应该是 O(N log(N)) 并且观察到的大型数组的时间与此一致。

无法从快速排序算法中获取处理时间

Cannot get processing time out of a quicksort algorithm

c