1 /* The MIT License 2 3 Copyright (c) 2008, 2011 Attractive Chaos <attractor@live.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 2011-04-10 (0.1.6): 28 29 * Added sample 30 31 2011-03 (0.1.5): 32 33 * Added shuffle/permutation 34 35 2008-11-16 (0.1.4): 36 37 * Fixed a bug in introsort() that happens in rare cases. 38 39 2008-11-05 (0.1.3): 40 41 * Fixed a bug in introsort() for complex comparisons. 42 43 * Fixed a bug in mergesort(). The previous version is not stable. 44 45 2008-09-15 (0.1.2): 46 47 * Accelerated introsort. On my Mac (not on another Linux machine), 48 my implementation is as fast as std::sort on random input. 49 50 * Added combsort and in introsort, switch to combsort if the 51 recursion is too deep. 52 53 2008-09-13 (0.1.1): 54 55 * Added k-small algorithm 56 57 2008-09-05 (0.1.0): 58 59 * Initial version 60 61 */ 62 63 #ifndef AC_KSORT_H 64 #define AC_KSORT_H 65 66 #include <stdlib.h> 67 #include <string.h> 68 69 #ifdef _WIN32 70 #define drand48() (rand() * (1.0 / RAND_MAX)) 71 #endif 72 73 typedef struct { 74 void *left, *right; 75 int depth; 76 } ks_isort_stack_t; 77 78 #define KSORT_SWAP(type_t, a, b) { register type_t t=(a); (a)=(b); (b)=t; } 79 80 #define KSORT_INIT(name, type_t, __sort_lt) \ 81 void ks_mergesort_##name(size_t n, type_t array[], type_t temp[]) \ 82 { \ 83 type_t *a2[2], *a, *b; \ 84 int curr, shift; \ 85 \ 86 a2[0] = array; \ 87 a2[1] = temp? temp : (type_t*)malloc(sizeof(type_t) * n); \ 88 for (curr = 0, shift = 0; (1ul<<shift) < n; ++shift) { \ 89 a = a2[curr]; b = a2[1-curr]; \ 90 if (shift == 0) { \ 91 type_t *p = b, *i, *eb = a + n; \ 92 for (i = a; i < eb; i += 2) { \ 93 if (i == eb - 1) *p++ = *i; \ 94 else { \ 95 if (__sort_lt(*(i+1), *i)) { \ 96 *p++ = *(i+1); *p++ = *i; \ 97 } else { \ 98 *p++ = *i; *p++ = *(i+1); \ 99 } \ 100 } \ 101 } \ 102 } else { \ 103 size_t i, step = 1ul<<shift; \ 104 for (i = 0; i < n; i += step<<1) { \ 105 type_t *p, *j, *k, *ea, *eb; \ 106 if (n < i + step) { \ 107 ea = a + n; eb = a; \ 108 } else { \ 109 ea = a + i + step; \ 110 eb = a + (n < i + (step<<1)? n : i + (step<<1)); \ 111 } \ 112 j = a + i; k = a + i + step; p = b + i; \ 113 while (j < ea && k < eb) { \ 114 if (__sort_lt(*k, *j)) *p++ = *k++; \ 115 else *p++ = *j++; \ 116 } \ 117 while (j < ea) *p++ = *j++; \ 118 while (k < eb) *p++ = *k++; \ 119 } \ 120 } \ 121 curr = 1 - curr; \ 122 } \ 123 if (curr == 1) { \ 124 type_t *p = a2[0], *i = a2[1], *eb = array + n; \ 125 for (; p < eb; ++i) *p++ = *i; \ 126 } \ 127 if (temp == 0) free(a2[1]); \ 128 } \ 129 void ks_heapadjust_##name(size_t i, size_t n, type_t l[]) \ 130 { \ 131 size_t k = i; \ 132 type_t tmp = l[i]; \ 133 while ((k = (k << 1) + 1) < n) { \ 134 if (k != n - 1 && __sort_lt(l[k], l[k+1])) ++k; \ 135 if (__sort_lt(l[k], tmp)) break; \ 136 l[i] = l[k]; i = k; \ 137 } \ 138 l[i] = tmp; \ 139 } \ 140 void ks_heapmake_##name(size_t lsize, type_t l[]) \ 141 { \ 142 size_t i; \ 143 for (i = (lsize >> 1) - 1; i != (size_t)(-1); --i) \ 144 ks_heapadjust_##name(i, lsize, l); \ 145 } \ 146 void ks_heapsort_##name(size_t lsize, type_t l[]) \ 147 { \ 148 size_t i; \ 149 for (i = lsize - 1; i > 0; --i) { \ 150 type_t tmp; \ 151 tmp = *l; *l = l[i]; l[i] = tmp; ks_heapadjust_##name(0, i, l); \ 152 } \ 153 } \ 154 static inline void __ks_insertsort_##name(type_t *s, type_t *t) \ 155 { \ 156 type_t *i, *j, swap_tmp; \ 157 for (i = s + 1; i < t; ++i) \ 158 for (j = i; j > s && __sort_lt(*j, *(j-1)); --j) { \ 159 swap_tmp = *j; *j = *(j-1); *(j-1) = swap_tmp; \ 160 } \ 161 } \ 162 void ks_combsort_##name(size_t n, type_t a[]) \ 163 { \ 164 const double shrink_factor = 1.2473309501039786540366528676643; \ 165 int do_swap; \ 166 size_t gap = n; \ 167 type_t tmp, *i, *j; \ 168 do { \ 169 if (gap > 2) { \ 170 gap = (size_t)(gap / shrink_factor); \ 171 if (gap == 9 || gap == 10) gap = 11; \ 172 } \ 173 do_swap = 0; \ 174 for (i = a; i < a + n - gap; ++i) { \ 175 j = i + gap; \ 176 if (__sort_lt(*j, *i)) { \ 177 tmp = *i; *i = *j; *j = tmp; \ 178 do_swap = 1; \ 179 } \ 180 } \ 181 } while (do_swap || gap > 2); \ 182 if (gap != 1) __ks_insertsort_##name(a, a + n); \ 183 } \ 184 void ks_introsort_##name(size_t n, type_t a[]) \ 185 { \ 186 int d; \ 187 ks_isort_stack_t *top, *stack; \ 188 type_t rp, swap_tmp; \ 189 type_t *s, *t, *i, *j, *k; \ 190 \ 191 if (n < 1) return; \ 192 else if (n == 2) { \ 193 if (__sort_lt(a[1], a[0])) { swap_tmp = a[0]; a[0] = a[1]; a[1] = swap_tmp; } \ 194 return; \ 195 } \ 196 for (d = 2; 1ul<<d < n; ++d); \ 197 stack = (ks_isort_stack_t*)malloc(sizeof(ks_isort_stack_t) * ((sizeof(size_t)*d)+2)); \ 198 top = stack; s = a; t = a + (n-1); d <<= 1; \ 199 while (1) { \ 200 if (s < t) { \ 201 if (--d == 0) { \ 202 ks_combsort_##name(t - s + 1, s); \ 203 t = s; \ 204 continue; \ 205 } \ 206 i = s; j = t; k = i + ((j-i)>>1) + 1; \ 207 if (__sort_lt(*k, *i)) { \ 208 if (__sort_lt(*k, *j)) k = j; \ 209 } else k = __sort_lt(*j, *i)? i : j; \ 210 rp = *k; \ 211 if (k != t) { swap_tmp = *k; *k = *t; *t = swap_tmp; } \ 212 for (;;) { \ 213 do ++i; while (__sort_lt(*i, rp)); \ 214 do --j; while (i <= j && __sort_lt(rp, *j)); \ 215 if (j <= i) break; \ 216 swap_tmp = *i; *i = *j; *j = swap_tmp; \ 217 } \ 218 swap_tmp = *i; *i = *t; *t = swap_tmp; \ 219 if (i-s > t-i) { \ 220 if (i-s > 16) { top->left = s; top->right = i-1; top->depth = d; ++top; } \ 221 s = t-i > 16? i+1 : t; \ 222 } else { \ 223 if (t-i > 16) { top->left = i+1; top->right = t; top->depth = d; ++top; } \ 224 t = i-s > 16? i-1 : s; \ 225 } \ 226 } else { \ 227 if (top == stack) { \ 228 free(stack); \ 229 __ks_insertsort_##name(a, a+n); \ 230 return; \ 231 } else { --top; s = (type_t*)top->left; t = (type_t*)top->right; d = top->depth; } \ 232 } \ 233 } \ 234 } \ 235 /* This function is adapted from: http://ndevilla.free.fr/median/ */ \ 236 /* 0 <= kk < n */ \ 237 type_t ks_ksmall_##name(size_t n, type_t arr[], size_t kk) \ 238 { \ 239 type_t *low, *high, *k, *ll, *hh, *mid; \ 240 low = arr; high = arr + n - 1; k = arr + kk; \ 241 for (;;) { \ 242 if (high <= low) return *k; \ 243 if (high == low + 1) { \ 244 if (__sort_lt(*high, *low)) KSORT_SWAP(type_t, *low, *high); \ 245 return *k; \ 246 } \ 247 mid = low + (high - low) / 2; \ 248 if (__sort_lt(*high, *mid)) KSORT_SWAP(type_t, *mid, *high); \ 249 if (__sort_lt(*high, *low)) KSORT_SWAP(type_t, *low, *high); \ 250 if (__sort_lt(*low, *mid)) KSORT_SWAP(type_t, *mid, *low); \ 251 KSORT_SWAP(type_t, *mid, *(low+1)); \ 252 ll = low + 1; hh = high; \ 253 for (;;) { \ 254 do ++ll; while (__sort_lt(*ll, *low)); \ 255 do --hh; while (__sort_lt(*low, *hh)); \ 256 if (hh < ll) break; \ 257 KSORT_SWAP(type_t, *ll, *hh); \ 258 } \ 259 KSORT_SWAP(type_t, *low, *hh); \ 260 if (hh <= k) low = ll; \ 261 if (hh >= k) high = hh - 1; \ 262 } \ 263 } \ 264 void ks_shuffle_##name(size_t n, type_t a[]) \ 265 { \ 266 int i, j; \ 267 for (i = n; i > 1; --i) { \ 268 type_t tmp; \ 269 j = (int)(drand48() * i); \ 270 tmp = a[j]; a[j] = a[i-1]; a[i-1] = tmp; \ 271 } \ 272 } \ 273 void ks_sample_##name(size_t n, size_t r, type_t a[]) /* FIXME: NOT TESTED!!! */ \ 274 { /* reference: http://code.activestate.com/recipes/272884/ */ \ 275 int i, k, pop = n; \ 276 for (i = (int)r, k = 0; i >= 0; --i) { \ 277 double z = 1., x = drand48(); \ 278 type_t tmp; \ 279 while (x < z) z -= z * i / (pop--); \ 280 if (k != n - pop - 1) tmp = a[k], a[k] = a[n-pop-1], a[n-pop-1] = tmp; \ 281 ++k; \ 282 } \ 283 } 284 285 #define ks_mergesort(name, n, a, t) ks_mergesort_##name(n, a, t) 286 #define ks_introsort(name, n, a) ks_introsort_##name(n, a) 287 #define ks_combsort(name, n, a) ks_combsort_##name(n, a) 288 #define ks_heapsort(name, n, a) ks_heapsort_##name(n, a) 289 #define ks_heapmake(name, n, a) ks_heapmake_##name(n, a) 290 #define ks_heapadjust(name, i, n, a) ks_heapadjust_##name(i, n, a) 291 #define ks_ksmall(name, n, a, k) ks_ksmall_##name(n, a, k) 292 #define ks_shuffle(name, n, a) ks_shuffle_##name(n, a) 293 294 #define ks_lt_generic(a, b) ((a) < (b)) 295 #define ks_lt_str(a, b) (strcmp((a), (b)) < 0) 296 297 typedef const char *ksstr_t; 298 299 #define KSORT_INIT_GENERIC(type_t) KSORT_INIT(type_t, type_t, ks_lt_generic) 300 #define KSORT_INIT_STR KSORT_INIT(str, ksstr_t, ks_lt_str) 301 302 #endif 303