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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
|
#ifndef LH3_ALGO_HH
#define LH3_ALGO_HH
// algorithm, C++ version. adapted from algo.h of C version.
typedef struct
{
size_t left,right;
} ALGO_QSortStack;
template<class ALGO_TYPE>
void algo_sort(size_t n, ALGO_TYPE a[])
{
size_t s, t, i, j, k;
ALGO_QSortStack *top, *stack;
ALGO_TYPE rp, swap_tmp;
if (n == 0) return;
/* stack = (ALGO_QSortStack*)malloc(sizeof(ALGO_QSortStack) * (size_t)((sizeof(size_t)*log(n)/ALGO_LOG2)+2)); */
stack = (ALGO_QSortStack*)malloc(sizeof(ALGO_QSortStack) * ((sizeof(size_t)*64)+2));
top = stack; s = 0; t = n-1;
while (1) {
if (s < t) {
i = s; j = t; k = (i+j)>>1; rp = a[k];
swap_tmp = a[k]; a[k] = a[t]; a[t] = swap_tmp;
do {
do { ++i; } while (a[i] < rp);
do { --j; } while (j && rp < a[j]);
swap_tmp = a[i]; a[i] = a[j]; a[j] = swap_tmp;
} while (i < j);
swap_tmp = a[i]; a[i] = a[j]; a[j] = swap_tmp;
swap_tmp = a[i]; a[i] = a[t]; a[t] = swap_tmp;
if (i-s > t-i) {
if (i-s > 9) { top->left = s; top->right = i-1; ++top; }
if (t-i > 9) s = i+1;
else s = t;
} else {
if (t-i > 9) { top->left = i+1; top->right = t; ++top; }
if (i-s > 9) t = i-1;
else t = s;
}
} else {
if (top == stack) {
free(stack);
for (i = 1; i < n; ++i)
for (j = i; j > 0 && a[j] < a[j-1]; --j) {
swap_tmp = a[j]; a[j] = a[j-1]; a[j-1] = swap_tmp;
}
return;
} else { --top; s = top->left; t = top->right; }
}
}
}
template<class TYPE>
inline void algo_swap(TYPE &a, TYPE &b)
{
TYPE c;
c = a; a = b; b = c;
}
template<class TYPE>
TYPE algo_ksmall(size_t n, TYPE array[], size_t k)
/* Return the kth smallest value in array array[0..n-1], The input array will be rearranged
* to have this value in array[k-1], with all smaller elements moved to arr[0..k-2] (in
* arbitrary order) and all larger elements in arr[k..n] (also in arbitrary order) */
{
TYPE *arr, a;
size_t i, ir, j, l, mid;
if (k == 0) k = 1;
arr = array - 1;
l = 1;
ir = n;
for (;;) {
if (ir <= l + 1) { /* Active partition contains 1 or 2 elements */
if (ir == l + 1 && arr[ir] < arr[l]) /* Case of 2 elements */
algo_swap(arr[l], arr[ir]);
return arr[k];
} else {
mid = (l + ir) >> 1;
algo_swap(arr[mid], arr[l+1]);
if (arr[ir] < arr[l]) algo_swap(arr[l], arr[ir]);
if (arr[ir] < arr[l+1]) algo_swap(arr[l+1], arr[ir]);
if (arr[l+1] < arr[l]) algo_swap(arr[l], arr[l+1]);
i = l + 1; /* initialize pointers for partitioning */
j = ir;
a = arr[l+1]; /* partition element */
for (;;) { /* beginning of innermost loop */
do ++i; while (arr[i] < a); /* scan up to find element > a */
do --j; while (a < arr[j]); /* scan down to find element < a */
if (j < i) break; /* Pointers crossed. Partitioning complete. */
algo_swap(arr[i], arr[j]);
}
arr[l+1] = arr[j]; /* insert partitioning element */
arr[j] = a;
if (j >= k) ir = j - 1; /* Keep active the partition that contains the kth element */
if (j <= k) l = i;
}
}
}
template<class TYPE>
void algo_shuffle(int n, TYPE *array)
{
int i;
TYPE tmp;
for (i = n - 1; i > 0; --i) {
int rand_ind = (int)(drand48() * i);
tmp = array[i]; array[i] = array[rand_ind]; array[rand_ind] = tmp;
}
}
// Heap related functions (binary heap)
template<class ALGO_TYPE>
inline void algo_heap_adjust(ALGO_TYPE l[], int i, int n)
{
int k;
ALGO_TYPE tmp = l[i];
for (;;) {
k = (i << 1) + 1; // the left child
if (k >= n) { l[i] = tmp; return; }
if (k < n - 1 && l[k] < l[k+1]) ++k;
if (tmp < l[k]) { l[i] = l[k]; i = k; }
else { l[i] = tmp; return; }
}
}
template<class ALGO_TYPE>
void algo_heap_make(ALGO_TYPE l[], int lsize)
{
for (int i = (lsize >> 1) - 1; i >= 0; --i)
algo_heap_adjust(l, i, lsize);
}
template<class ALGO_TYPE>
void algo_heap_sort(ALGO_TYPE l[], int lsize)
{
ALGO_TYPE swap_tmp;
for (int i = lsize - 1; i > 0; --i) {
ALGO_TYPE swap_tmp = l[0];
l[0] = l[i]; l[i] = swap_tmp;
algo_heap_adjust(l, 0, i);
}
}
#endif /* LH3_ALGO_HH */
|
