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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
|
#include "threadpool.h"
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
static size_t partition(int v[], size_t len);
/* TODO: quicksort-Implementation parallelisieren */
static void quicksort(int list[], size_t len) {
if (len <= 1) return;
size_t mid = partition(list, len);
quicksort(list, mid);
quicksort(list + mid + 1, len - mid - 1);
}
size_t partition(int v[], size_t len) {
size_t pivot = len - 1;
size_t l = 0, r = len - 2;
int t;
while (1) {
while (l < r && v[l] < v[pivot]) ++l;
while (l < r && v[r] >= v[pivot]) --r;
if (l >= r) break;
t = v[l];
v[l] = v[r];
v[r] = t;
}
if (v[l] >= v[pivot]) {
t = v[l];
v[l] = v[pivot];
v[pivot] = t;
return l;
}
return pivot;
}
static void list_randomize(int list[], size_t len) {
for (int *p = list, *e = p + len; p < e; ++p)
*p = (int)(((((double) rand()) / RAND_MAX) - 0.5)) * (int)(len);
}
static void list_print(int list[], size_t len) {
const char *sep = "";
fputs("(", stdout);
for (int *p = list, *e = p + len; p < e; ++p, sep = ", ")
printf("%s%i", sep, *p);
fputs(")\n", stdout);
}
static int list_is_sorted(int list[], size_t len) {
for (int *p = list, *e = p + len - 1; p < e; ++p) {
if (p[0] > p[1])
return 0;
}
return 1;
}
static struct timespec time_diff(struct timespec t1, struct timespec t2) {
struct timespec result = {
.tv_sec = t2.tv_sec - t1.tv_sec,
.tv_nsec = t2.tv_nsec - t1.tv_nsec
};
if (t2.tv_nsec - t1.tv_nsec < 0) {
result.tv_sec = t2.tv_sec - t1.tv_sec - 1;
result.tv_nsec = 1000000000l + t2.tv_nsec - t1.tv_nsec;
}
return result;
}
int main(int argc, const char *argv[]) {
if (tpInit(8) != 0)
perror("Thread Pool initialization failed"), exit(-1);
atexit(&tpRelease);
/* read the length of the list from the command line */
size_t list_len = 30000000;
if (argc >= 2) {
long arg = strtol(argv[1], (char **)&argv[strlen(argv[1])], 10);
if (arg > 0)
list_len = (size_t)arg;
}
/* generate a list with random integers */
int *list = malloc(sizeof(int) * list_len);
list_randomize(list, list_len);
printf("Len: %lu\n", list_len);
/* print the unsorted list if it's not too long */
printf("---- Unsortiert: %i ----\n", list_is_sorted(list, list_len));
if (list_len <= 100)
list_print(list, list_len);
/* sort it and print the sorted list if it's not too long */
struct timespec start, end, dt;
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);
quicksort(list, list_len);
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end);
dt = time_diff(start, end);
printf("---- Sortiert: %i ----\n", list_is_sorted(list, list_len));
if (list_len <= 100)
list_print(list, list_len);
printf("Dauer: %lis %lins\n", dt.tv_sec, dt.tv_nsec);
return 0;
}
|
