|
0
|
1 /* The MIT License
|
|
|
2
|
|
|
3 Copyright (c) 2008, by Attractive Chaos <attractivechaos@aol.co.uk>
|
|
|
4
|
|
|
5 Permission is hereby granted, free of charge, to any person obtaining
|
|
|
6 a copy of this software and associated documentation files (the
|
|
|
7 "Software"), to deal in the Software without restriction, including
|
|
|
8 without limitation the rights to use, copy, modify, merge, publish,
|
|
|
9 distribute, sublicense, and/or sell copies of the Software, and to
|
|
|
10 permit persons to whom the Software is furnished to do so, subject to
|
|
|
11 the following conditions:
|
|
|
12
|
|
|
13 The above copyright notice and this permission notice shall be
|
|
|
14 included in all copies or substantial portions of the Software.
|
|
|
15
|
|
|
16 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
|
|
|
17 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
|
|
|
18 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
|
|
|
19 NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
|
|
|
20 BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
|
|
|
21 ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
|
|
|
22 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
|
|
|
23 SOFTWARE.
|
|
|
24 */
|
|
|
25
|
|
|
26 /*
|
|
|
27 2008-11-16 (0.1.4):
|
|
|
28
|
|
|
29 * Fixed a bug in introsort() that happens in rare cases.
|
|
|
30
|
|
|
31 2008-11-05 (0.1.3):
|
|
|
32
|
|
|
33 * Fixed a bug in introsort() for complex comparisons.
|
|
|
34
|
|
|
35 * Fixed a bug in mergesort(). The previous version is not stable.
|
|
|
36
|
|
|
37 2008-09-15 (0.1.2):
|
|
|
38
|
|
|
39 * Accelerated introsort. On my Mac (not on another Linux machine),
|
|
|
40 my implementation is as fast as std::sort on random input.
|
|
|
41
|
|
|
42 * Added combsort and in introsort, switch to combsort if the
|
|
|
43 recursion is too deep.
|
|
|
44
|
|
|
45 2008-09-13 (0.1.1):
|
|
|
46
|
|
|
47 * Added k-small algorithm
|
|
|
48
|
|
|
49 2008-09-05 (0.1.0):
|
|
|
50
|
|
|
51 * Initial version
|
|
|
52
|
|
|
53 */
|
|
|
54
|
|
|
55 #ifndef AC_KSORT_H
|
|
|
56 #define AC_KSORT_H
|
|
|
57
|
|
|
58 #include <stdlib.h>
|
|
|
59 #include <string.h>
|
|
|
60
|
|
|
61 typedef struct {
|
|
|
62 void *left, *right;
|
|
|
63 int depth;
|
|
|
64 } ks_isort_stack_t;
|
|
|
65
|
|
|
66 #define KSORT_SWAP(type_t, a, b) { register type_t t=(a); (a)=(b); (b)=t; }
|
|
|
67
|
|
|
68 #define KSORT_INIT(name, type_t, __sort_lt) \
|
|
|
69 void ks_mergesort_##name(size_t n, type_t array[], type_t temp[]) \
|
|
|
70 { \
|
|
|
71 type_t *a2[2], *a, *b; \
|
|
|
72 int curr, shift; \
|
|
|
73 \
|
|
|
74 a2[0] = array; \
|
|
|
75 a2[1] = temp? temp : (type_t*)malloc(sizeof(type_t) * n); \
|
|
|
76 for (curr = 0, shift = 0; (1ul<<shift) < n; ++shift) { \
|
|
|
77 a = a2[curr]; b = a2[1-curr]; \
|
|
|
78 if (shift == 0) { \
|
|
|
79 type_t *p = b, *i, *eb = a + n; \
|
|
|
80 for (i = a; i < eb; i += 2) { \
|
|
|
81 if (i == eb - 1) *p++ = *i; \
|
|
|
82 else { \
|
|
|
83 if (__sort_lt(*(i+1), *i)) { \
|
|
|
84 *p++ = *(i+1); *p++ = *i; \
|
|
|
85 } else { \
|
|
|
86 *p++ = *i; *p++ = *(i+1); \
|
|
|
87 } \
|
|
|
88 } \
|
|
|
89 } \
|
|
|
90 } else { \
|
|
|
91 size_t i, step = 1ul<<shift; \
|
|
|
92 for (i = 0; i < n; i += step<<1) { \
|
|
|
93 type_t *p, *j, *k, *ea, *eb; \
|
|
|
94 if (n < i + step) { \
|
|
|
95 ea = a + n; eb = a; \
|
|
|
96 } else { \
|
|
|
97 ea = a + i + step; \
|
|
|
98 eb = a + (n < i + (step<<1)? n : i + (step<<1)); \
|
|
|
99 } \
|
|
|
100 j = a + i; k = a + i + step; p = b + i; \
|
|
|
101 while (j < ea && k < eb) { \
|
|
|
102 if (__sort_lt(*k, *j)) *p++ = *k++; \
|
|
|
103 else *p++ = *j++; \
|
|
|
104 } \
|
|
|
105 while (j < ea) *p++ = *j++; \
|
|
|
106 while (k < eb) *p++ = *k++; \
|
|
|
107 } \
|
|
|
108 } \
|
|
|
109 curr = 1 - curr; \
|
|
|
110 } \
|
|
|
111 if (curr == 1) { \
|
|
|
112 type_t *p = a2[0], *i = a2[1], *eb = array + n; \
|
|
|
113 for (; p < eb; ++i) *p++ = *i; \
|
|
|
114 } \
|
|
|
115 if (temp == 0) free(a2[1]); \
|
|
|
116 } \
|
|
|
117 void ks_heapadjust_##name(size_t i, size_t n, type_t l[]) \
|
|
|
118 { \
|
|
|
119 size_t k = i; \
|
|
|
120 type_t tmp = l[i]; \
|
|
|
121 while ((k = (k << 1) + 1) < n) { \
|
|
|
122 if (k != n - 1 && __sort_lt(l[k], l[k+1])) ++k; \
|
|
|
123 if (__sort_lt(l[k], tmp)) break; \
|
|
|
124 l[i] = l[k]; i = k; \
|
|
|
125 } \
|
|
|
126 l[i] = tmp; \
|
|
|
127 } \
|
|
|
128 void ks_heapmake_##name(size_t lsize, type_t l[]) \
|
|
|
129 { \
|
|
|
130 size_t i; \
|
|
|
131 for (i = (lsize >> 1) - 1; i != (size_t)(-1); --i) \
|
|
|
132 ks_heapadjust_##name(i, lsize, l); \
|
|
|
133 } \
|
|
|
134 void ks_heapsort_##name(size_t lsize, type_t l[]) \
|
|
|
135 { \
|
|
|
136 size_t i; \
|
|
|
137 for (i = lsize - 1; i > 0; --i) { \
|
|
|
138 type_t tmp; \
|
|
|
139 tmp = *l; *l = l[i]; l[i] = tmp; ks_heapadjust_##name(0, i, l); \
|
|
|
140 } \
|
|
|
141 } \
|
|
|
142 inline void __ks_insertsort_##name(type_t *s, type_t *t) \
|
|
|
143 { \
|
|
|
144 type_t *i, *j, swap_tmp; \
|
|
|
145 for (i = s + 1; i < t; ++i) \
|
|
|
146 for (j = i; j > s && __sort_lt(*j, *(j-1)); --j) { \
|
|
|
147 swap_tmp = *j; *j = *(j-1); *(j-1) = swap_tmp; \
|
|
|
148 } \
|
|
|
149 } \
|
|
|
150 void ks_combsort_##name(size_t n, type_t a[]) \
|
|
|
151 { \
|
|
|
152 const double shrink_factor = 1.2473309501039786540366528676643; \
|
|
|
153 int do_swap; \
|
|
|
154 size_t gap = n; \
|
|
|
155 type_t tmp, *i, *j; \
|
|
|
156 do { \
|
|
|
157 if (gap > 2) { \
|
|
|
158 gap = (size_t)(gap / shrink_factor); \
|
|
|
159 if (gap == 9 || gap == 10) gap = 11; \
|
|
|
160 } \
|
|
|
161 do_swap = 0; \
|
|
|
162 for (i = a; i < a + n - gap; ++i) { \
|
|
|
163 j = i + gap; \
|
|
|
164 if (__sort_lt(*j, *i)) { \
|
|
|
165 tmp = *i; *i = *j; *j = tmp; \
|
|
|
166 do_swap = 1; \
|
|
|
167 } \
|
|
|
168 } \
|
|
|
169 } while (do_swap || gap > 2); \
|
|
|
170 if (gap != 1) __ks_insertsort_##name(a, a + n); \
|
|
|
171 } \
|
|
|
172 void ks_introsort_##name(size_t n, type_t a[]) \
|
|
|
173 { \
|
|
|
174 int d; \
|
|
|
175 ks_isort_stack_t *top, *stack; \
|
|
|
176 type_t rp, swap_tmp; \
|
|
|
177 type_t *s, *t, *i, *j, *k; \
|
|
|
178 \
|
|
|
179 if (n < 1) return; \
|
|
|
180 else if (n == 2) { \
|
|
|
181 if (__sort_lt(a[1], a[0])) { swap_tmp = a[0]; a[0] = a[1]; a[1] = swap_tmp; } \
|
|
|
182 return; \
|
|
|
183 } \
|
|
|
184 for (d = 2; 1ul<<d < n; ++d); \
|
|
|
185 stack = (ks_isort_stack_t*)malloc(sizeof(ks_isort_stack_t) * ((sizeof(size_t)*d)+2)); \
|
|
|
186 top = stack; s = a; t = a + (n-1); d <<= 1; \
|
|
|
187 while (1) { \
|
|
|
188 if (s < t) { \
|
|
|
189 if (--d == 0) { \
|
|
|
190 ks_combsort_##name(t - s + 1, s); \
|
|
|
191 t = s; \
|
|
|
192 continue; \
|
|
|
193 } \
|
|
|
194 i = s; j = t; k = i + ((j-i)>>1) + 1; \
|
|
|
195 if (__sort_lt(*k, *i)) { \
|
|
|
196 if (__sort_lt(*k, *j)) k = j; \
|
|
|
197 } else k = __sort_lt(*j, *i)? i : j; \
|
|
|
198 rp = *k; \
|
|
|
199 if (k != t) { swap_tmp = *k; *k = *t; *t = swap_tmp; } \
|
|
|
200 for (;;) { \
|
|
|
201 do ++i; while (__sort_lt(*i, rp)); \
|
|
|
202 do --j; while (i <= j && __sort_lt(rp, *j)); \
|
|
|
203 if (j <= i) break; \
|
|
|
204 swap_tmp = *i; *i = *j; *j = swap_tmp; \
|
|
|
205 } \
|
|
|
206 swap_tmp = *i; *i = *t; *t = swap_tmp; \
|
|
|
207 if (i-s > t-i) { \
|
|
|
208 if (i-s > 16) { top->left = s; top->right = i-1; top->depth = d; ++top; } \
|
|
|
209 s = t-i > 16? i+1 : t; \
|
|
|
210 } else { \
|
|
|
211 if (t-i > 16) { top->left = i+1; top->right = t; top->depth = d; ++top; } \
|
|
|
212 t = i-s > 16? i-1 : s; \
|
|
|
213 } \
|
|
|
214 } else { \
|
|
|
215 if (top == stack) { \
|
|
|
216 free(stack); \
|
|
|
217 __ks_insertsort_##name(a, a+n); \
|
|
|
218 return; \
|
|
|
219 } else { --top; s = (type_t*)top->left; t = (type_t*)top->right; d = top->depth; } \
|
|
|
220 } \
|
|
|
221 } \
|
|
|
222 } \
|
|
|
223 /* This function is adapted from: http://ndevilla.free.fr/median/ */ \
|
|
|
224 /* 0 <= kk < n */ \
|
|
|
225 type_t ks_ksmall_##name(size_t n, type_t arr[], size_t kk) \
|
|
|
226 { \
|
|
|
227 type_t *low, *high, *k, *ll, *hh, *mid; \
|
|
|
228 low = arr; high = arr + n - 1; k = arr + kk; \
|
|
|
229 for (;;) { \
|
|
|
230 if (high <= low) return *k; \
|
|
|
231 if (high == low + 1) { \
|
|
|
232 if (__sort_lt(*high, *low)) KSORT_SWAP(type_t, *low, *high); \
|
|
|
233 return *k; \
|
|
|
234 } \
|
|
|
235 mid = low + (high - low) / 2; \
|
|
|
236 if (__sort_lt(*high, *mid)) KSORT_SWAP(type_t, *mid, *high); \
|
|
|
237 if (__sort_lt(*high, *low)) KSORT_SWAP(type_t, *low, *high); \
|
|
|
238 if (__sort_lt(*low, *mid)) KSORT_SWAP(type_t, *mid, *low); \
|
|
|
239 KSORT_SWAP(type_t, *mid, *(low+1)); \
|
|
|
240 ll = low + 1; hh = high; \
|
|
|
241 for (;;) { \
|
|
|
242 do ++ll; while (__sort_lt(*ll, *low)); \
|
|
|
243 do --hh; while (__sort_lt(*low, *hh)); \
|
|
|
244 if (hh < ll) break; \
|
|
|
245 KSORT_SWAP(type_t, *ll, *hh); \
|
|
|
246 } \
|
|
|
247 KSORT_SWAP(type_t, *low, *hh); \
|
|
|
248 if (hh <= k) low = ll; \
|
|
|
249 if (hh >= k) high = hh - 1; \
|
|
|
250 } \
|
|
|
251 }
|
|
|
252
|
|
|
253 #define ks_mergesort(name, n, a, t) ks_mergesort_##name(n, a, t)
|
|
|
254 #define ks_introsort(name, n, a) ks_introsort_##name(n, a)
|
|
|
255 #define ks_combsort(name, n, a) ks_combsort_##name(n, a)
|
|
|
256 #define ks_heapsort(name, n, a) ks_heapsort_##name(n, a)
|
|
|
257 #define ks_heapmake(name, n, a) ks_heapmake_##name(n, a)
|
|
|
258 #define ks_heapadjust(name, i, n, a) ks_heapadjust_##name(i, n, a)
|
|
|
259 #define ks_ksmall(name, n, a, k) ks_ksmall_##name(n, a, k)
|
|
|
260
|
|
|
261 #define ks_lt_generic(a, b) ((a) < (b))
|
|
|
262 #define ks_lt_str(a, b) (strcmp((a), (b)) < 0)
|
|
|
263
|
|
|
264 typedef const char *ksstr_t;
|
|
|
265
|
|
|
266 #define KSORT_INIT_GENERIC(type_t) KSORT_INIT(type_t, type_t, ks_lt_generic)
|
|
|
267 #define KSORT_INIT_STR KSORT_INIT(str, ksstr_t, ks_lt_str)
|
|
|
268
|
|
|
269 #endif
|
