Cannot get processing time out of a quicksort algorithm-CodePudding

I've been trying to get the processing time of a sorting algorithm via clock_t start, end;

But the console outputs nothing. I've been hitting this brick wall for a while and need help.

Program in question

// 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;
}

Could someone tell me what I am doing wrong, please?

Edit: Dumbass me forgot to add an orderly array. So, int a[NUM]; is now int a[NUM]={1,2,3,4,5,6,7,8,9]; New problem, changing NUM does not change the process time. What can I do to fix this?

CodePudding user response：

There are multiple problems in your code:

x = (a[i] a[j]) / 2; may overflow, which has undefined behavior, and produce a value that is not even between a[i] and a[j], potentially causing an infinite recursion.
int a[NUM]; is not initialized
the REPEAT loop produces a value of n with computations that will likely overflow and that is not used, the code is probably removed by the optimizing compiler.

You must be careful to compute the mid point without overflow. If type long long is larger than int, you can use:

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

Here is a modified version, benchmarking various distributions:

//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("s", "length");
    for (i = 0; i < 7; i  )
        printf("%9s ", name[i]);
    printf("\n");
    for (j = 0, len = max; j < k; j  , len /= 10) {
        printf("d", len);
        for (i = 0; i < 7; i  )
            printf(" %9.3f", c[j][i] * 1000.0 / CLOCKS_PER_SEC);
        printf("\n");
    }
    return 0;
}

Output for 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

As you can see, the timings are quite different depending on the distribution of numbers. A random distribution causing the most mispredictions in the scanning loops, hence is slower than one with substantial numbers of duplicates, and sorted arrays are even faster because the comparisons are well predicted and fewer swaps occur.

The time complexity should be O(N log(N)) on average and the observed timings for large arrays are consistent with this.