1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
|
// Generic Quicksort in C, performs as fast as c++ std::sort().
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#ifdef __cplusplus
#include <algorithm>
#endif
#define i_val int
#include <stc/algo/csort.h>
#define ROTL(d,bits) ((d<<(bits)) | (d>>(8*sizeof(d)-(bits))))
uint64_t romutrio(uint64_t s[3]) {
uint64_t xp = s[0], yp = s[1], zp = s[2];
s[0] = 15241094284759029579u * zp;
s[1] = yp - xp; s[1] = ROTL(s[1], 12);
s[2] = zp - yp; s[2] = ROTL(s[2], 44);
return xp;
}
static int cmp_int(const void* a, const void* b) {
return c_default_cmp((const int*)a, (const int*)b);
}
void testsort(int *a, int size, const char *desc) {
clock_t t = clock();
#ifdef __cplusplus
printf("std::sort: "); std::sort(a, a + size);
#elif defined QSORT
printf("qsort: "); qsort(a, size, sizeof *a, cmp_int);
#else
printf("stc_sort: "); csort_int(a, size);
#endif
t = clock() - t;
printf("time: %.1fms, n: %d, %s\n",
(double)t*1000.0/CLOCKS_PER_SEC, size, desc);
}
int main(int argc, char *argv[]) {
size_t i, size = argc > 1 ? strtoull(argv[1], NULL, 0) : 10000000;
uint64_t s[3] = {123456789, 3456789123, 789123456};
int32_t *a = (int32_t*)malloc(sizeof(*a) * size);
if (!a) return -1;
for (i = 0; i < size; i++)
a[i] = romutrio(s) & (1U << 30) - 1;
testsort(a, size, "random");
for (i = 0; i < 20; i++)
printf(" %d", (int)a[i]);
puts("");
for (i = 0; i < size; i++)
a[i] = i;
testsort(a, size, "sorted");
for (i = 0; i < size; i++)
a[i] = size - i;
testsort(a, size, "reverse sorted");
for (i = 0; i < size; i++)
a[i] = 126735;
testsort(a, size, "constant");
for (i = 0; i < size; i++)
a[i] = i + 1;
a[size - 1] = 0;
testsort(a, size, "rotated");
free(a);
}
|
