/
quick.c
122 lines (92 loc) · 2.97 KB
/
quick.c
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
122
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// code for SIR on networks by Petter Holme (2018)
// an augmented quicksort to sort the contact time arrays in decreasing order
// of their last elements . . this is needed to cut the search of inactive
// neighbors
// include header file
#include "run.h"
// define constant
#define CUTOFF 10
// define macros
#define V(x) (nme->t[(x)][nme->nc[(x)] - 1])
#define SWAP(x,y) {utmp = nme->nc[(x)]; nme->nc[(x)] = nme->nc[(y)]; nme->nc[(y)] = utmp; utmp = nme->nb[(x)]; nme->nb[(x)] = nme->nb[(y)]; nme->nb[(y)] = utmp; uptmp = nme->t[(x)]; nme->t[(x)] = nme->t[(y)]; nme->t[(y)] = uptmp;}
// declare pointer n to NODE struct (that has been defined elsewhere)
extern struct NODE *n;
// define struct PIVOTS
struct PIVOTS {unsigned int left, right;} PIVOTS;
// declare utmp and *uptmp (pointer)
unsigned int utmp, *uptmp;
// nme is a pointer to NODE struct
struct NODE *nme;
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// to speed up the search for almost sorted arrays
void insertion_sort (int left, int right) {
int i, j;
unsigned int snb, snc, *st, save;
for (i = left + 1; i < right; i++) {
snb = nme->nb[i];
snc = nme->nc[i];
st = nme->t[i];
save = V(i);
for (j = i; (j > 0) && (V(j - 1) < save); j--) {
nme->nb[j] = nme->nb[j - 1];
nme->nc[j] = nme->nc[j - 1];
nme->t[j] = nme->t[j - 1];
}
nme->nb[j] = snb;
nme->nc[j] = snc;
nme->t[j] = st;
}
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
unsigned int median (int left, int right) {
int mid = (left + right) >> 1;
if (V(left) < V(mid)) SWAP(left, mid);
if (V(left) < V(right)) SWAP(left, right);
if (V(mid) < V(right)) SWAP(mid, right);
SWAP(mid, right - 1);
return V(right - 1);
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
struct PIVOTS q_partition (int left, int right) {
int i = left, j = right - 1, k, m = left, n = right - 1;
unsigned int pivot = median(left, right);
struct PIVOTS ret;
for ( ; ; ) {
do i++; while (V(i) > pivot);
do j--; while ((V(j) < pivot) && (j > left));
if (i >= j) break;
SWAP(i, j);
if (V(i) == pivot) {
m++;
SWAP(m, i);
}
if (V(j) == pivot) {
n--;
SWAP(n, j);
}
}
SWAP(i, right - 1);
j = i - 1;
i++;
for (k = left; k < m; k++, j--) SWAP(k, j);
for (k = right - 1; k > n; k--, i++) SWAP(k, i);
ret.left = i;
ret.right = j;
return ret;
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
void quicksort_r (int left, int right) {
if (left + CUTOFF <= right) {
struct PIVOTS pivot = q_partition(left, right);
quicksort_r(left, pivot.right);
quicksort_r(pivot.left, right);
}
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
void quick (unsigned int i) {
nme = n + i;
quicksort_r(0, nme->deg - 1);
insertion_sort(0, nme->deg);
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -