| 1 |
/* The MIT License |
| 2 |
|
| 3 |
Copyright (c) 2008, by Attractive Chaos <[email protected]> |
| 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 |
#ifdef USE_MALLOC_WRAPPERS |
| 62 |
# include "malloc_wrap.h" |
| 63 |
#endif |
| 64 |
|
| 65 |
typedef struct { |
| 66 |
void *left, *right; |
| 67 |
int depth; |
| 68 |
} ks_isort_stack_t; |
| 69 |
|
| 70 |
#define KSORT_SWAP(type_t, a, b) { register type_t t=(a); (a)=(b); (b)=t; } |
| 71 |
|
| 72 |
#define KSORT_INIT(name, type_t, __sort_lt) \ |
| 73 |
void ks_mergesort_##name(size_t n, type_t array[], type_t temp[]) \ |
| 74 |
{ \ |
| 75 |
type_t *a2[2], *a, *b; \ |
| 76 |
int curr, shift; \ |
| 77 |
\ |
| 78 |
a2[0] = array; \ |
| 79 |
a2[1] = temp? temp : (type_t*)malloc(sizeof(type_t) * n); \ |
| 80 |
for (curr = 0, shift = 0; (1ul<<shift) < n; ++shift) { \ |
| 81 |
a = a2[curr]; b = a2[1-curr]; \ |
| 82 |
if (shift == 0) { \ |
| 83 |
type_t *p = b, *i, *eb = a + n; \ |
| 84 |
for (i = a; i < eb; i += 2) { \ |
| 85 |
if (i == eb - 1) *p++ = *i; \ |
| 86 |
else { \ |
| 87 |
if (__sort_lt(*(i+1), *i)) { \ |
| 88 |
*p++ = *(i+1); *p++ = *i; \ |
| 89 |
} else { \ |
| 90 |
*p++ = *i; *p++ = *(i+1); \ |
| 91 |
} \ |
| 92 |
} \ |
| 93 |
} \ |
| 94 |
} else { \ |
| 95 |
size_t i, step = 1ul<<shift; \ |
| 96 |
for (i = 0; i < n; i += step<<1) { \ |
| 97 |
type_t *p, *j, *k, *ea, *eb; \ |
| 98 |
if (n < i + step) { \ |
| 99 |
ea = a + n; eb = a; \ |
| 100 |
} else { \ |
| 101 |
ea = a + i + step; \ |
| 102 |
eb = a + (n < i + (step<<1)? n : i + (step<<1)); \ |
| 103 |
} \ |
| 104 |
j = a + i; k = a + i + step; p = b + i; \ |
| 105 |
while (j < ea && k < eb) { \ |
| 106 |
if (__sort_lt(*k, *j)) *p++ = *k++; \ |
| 107 |
else *p++ = *j++; \ |
| 108 |
} \ |
| 109 |
while (j < ea) *p++ = *j++; \ |
| 110 |
while (k < eb) *p++ = *k++; \ |
| 111 |
} \ |
| 112 |
} \ |
| 113 |
curr = 1 - curr; \ |
| 114 |
} \ |
| 115 |
if (curr == 1) { \ |
| 116 |
type_t *p = a2[0], *i = a2[1], *eb = array + n; \ |
| 117 |
for (; p < eb; ++i) *p++ = *i; \ |
| 118 |
} \ |
| 119 |
if (temp == 0) free(a2[1]); \ |
| 120 |
} \ |
| 121 |
void ks_heapadjust_##name(size_t i, size_t n, type_t l[]) \ |
| 122 |
{ \ |
| 123 |
size_t k = i; \ |
| 124 |
type_t tmp = l[i]; \ |
| 125 |
while ((k = (k << 1) + 1) < n) { \ |
| 126 |
if (k != n - 1 && __sort_lt(l[k], l[k+1])) ++k; \ |
| 127 |
if (__sort_lt(l[k], tmp)) break; \ |
| 128 |
l[i] = l[k]; i = k; \ |
| 129 |
} \ |
| 130 |
l[i] = tmp; \ |
| 131 |
} \ |
| 132 |
void ks_heapmake_##name(size_t lsize, type_t l[]) \ |
| 133 |
{ \ |
| 134 |
size_t i; \ |
| 135 |
for (i = (lsize >> 1) - 1; i != (size_t)(-1); --i) \ |
| 136 |
ks_heapadjust_##name(i, lsize, l); \ |
| 137 |
} \ |
| 138 |
void ks_heapsort_##name(size_t lsize, type_t l[]) \ |
| 139 |
{ \ |
| 140 |
size_t i; \ |
| 141 |
for (i = lsize - 1; i > 0; --i) { \ |
| 142 |
type_t tmp; \ |
| 143 |
tmp = *l; *l = l[i]; l[i] = tmp; ks_heapadjust_##name(0, i, l); \ |
| 144 |
} \ |
| 145 |
} \ |
| 146 |
static inline void __ks_insertsort_##name(type_t *s, type_t *t) \ |
| 147 |
{ \ |
| 148 |
type_t *i, *j, swap_tmp; \ |
| 149 |
for (i = s + 1; i < t; ++i) \ |
| 150 |
for (j = i; j > s && __sort_lt(*j, *(j-1)); --j) { \ |
| 151 |
swap_tmp = *j; *j = *(j-1); *(j-1) = swap_tmp; \ |
| 152 |
} \ |
| 153 |
} \ |
| 154 |
void ks_combsort_##name(size_t n, type_t a[]) \ |
| 155 |
{ \ |
| 156 |
const double shrink_factor = 1.2473309501039786540366528676643; \ |
| 157 |
int do_swap; \ |
| 158 |
size_t gap = n; \ |
| 159 |
type_t tmp, *i, *j; \ |
| 160 |
do { \ |
| 161 |
if (gap > 2) { \ |
| 162 |
gap = (size_t)(gap / shrink_factor); \ |
| 163 |
if (gap == 9 || gap == 10) gap = 11; \ |
| 164 |
} \ |
| 165 |
do_swap = 0; \ |
| 166 |
for (i = a; i < a + n - gap; ++i) { \ |
| 167 |
j = i + gap; \ |
| 168 |
if (__sort_lt(*j, *i)) { \ |
| 169 |
tmp = *i; *i = *j; *j = tmp; \ |
| 170 |
do_swap = 1; \ |
| 171 |
} \ |
| 172 |
} \ |
| 173 |
} while (do_swap || gap > 2); \ |
| 174 |
if (gap != 1) __ks_insertsort_##name(a, a + n); \ |
| 175 |
} \ |
| 176 |
void ks_introsort_##name(size_t n, type_t a[]) \ |
| 177 |
{ \ |
| 178 |
int d; \ |
| 179 |
ks_isort_stack_t *top, *stack; \ |
| 180 |
type_t rp, swap_tmp; \ |
| 181 |
type_t *s, *t, *i, *j, *k; \ |
| 182 |
\ |
| 183 |
if (n < 1) return; \ |
| 184 |
else if (n == 2) { \ |
| 185 |
if (__sort_lt(a[1], a[0])) { swap_tmp = a[0]; a[0] = a[1]; a[1] = swap_tmp; } \ |
| 186 |
return; \ |
| 187 |
} \ |
| 188 |
for (d = 2; 1ul<<d < n; ++d); \ |
| 189 |
stack = (ks_isort_stack_t*)malloc(sizeof(ks_isort_stack_t) * ((sizeof(size_t)*d)+2)); \ |
| 190 |
top = stack; s = a; t = a + (n-1); d <<= 1; \ |
| 191 |
while (1) { \ |
| 192 |
if (s < t) { \ |
| 193 |
if (--d == 0) { \ |
| 194 |
ks_combsort_##name(t - s + 1, s); \ |
| 195 |
t = s; \ |
| 196 |
continue; \ |
| 197 |
} \ |
| 198 |
i = s; j = t; k = i + ((j-i)>>1) + 1; \ |
| 199 |
if (__sort_lt(*k, *i)) { \ |
| 200 |
if (__sort_lt(*k, *j)) k = j; \ |
| 201 |
} else k = __sort_lt(*j, *i)? i : j; \ |
| 202 |
rp = *k; \ |
| 203 |
if (k != t) { swap_tmp = *k; *k = *t; *t = swap_tmp; } \ |
| 204 |
for (;;) { \ |
| 205 |
do ++i; while (__sort_lt(*i, rp)); \ |
| 206 |
do --j; while (i <= j && __sort_lt(rp, *j)); \ |
| 207 |
if (j <= i) break; \ |
| 208 |
swap_tmp = *i; *i = *j; *j = swap_tmp; \ |
| 209 |
} \ |
| 210 |
swap_tmp = *i; *i = *t; *t = swap_tmp; \ |
| 211 |
if (i-s > t-i) { \ |
| 212 |
if (i-s > 16) { top->left = s; top->right = i-1; top->depth = d; ++top; } \ |
| 213 |
s = t-i > 16? i+1 : t; \ |
| 214 |
} else { \ |
| 215 |
if (t-i > 16) { top->left = i+1; top->right = t; top->depth = d; ++top; } \ |
| 216 |
t = i-s > 16? i-1 : s; \ |
| 217 |
} \ |
| 218 |
} else { \ |
| 219 |
if (top == stack) { \ |
| 220 |
free(stack); \ |
| 221 |
__ks_insertsort_##name(a, a+n); \ |
| 222 |
return; \ |
| 223 |
} else { --top; s = (type_t*)top->left; t = (type_t*)top->right; d = top->depth; } \ |
| 224 |
} \ |
| 225 |
} \ |
| 226 |
} \ |
| 227 |
/* This function is adapted from: http://ndevilla.free.fr/median/ */ \ |
| 228 |
/* 0 <= kk < n */ \ |
| 229 |
type_t ks_ksmall_##name(size_t n, type_t arr[], size_t kk) \ |
| 230 |
{ \ |
| 231 |
type_t *low, *high, *k, *ll, *hh, *mid; \ |
| 232 |
low = arr; high = arr + n - 1; k = arr + kk; \ |
| 233 |
for (;;) { \ |
| 234 |
if (high <= low) return *k; \ |
| 235 |
if (high == low + 1) { \ |
| 236 |
if (__sort_lt(*high, *low)) KSORT_SWAP(type_t, *low, *high); \ |
| 237 |
return *k; \ |
| 238 |
} \ |
| 239 |
mid = low + (high - low) / 2; \ |
| 240 |
if (__sort_lt(*high, *mid)) KSORT_SWAP(type_t, *mid, *high); \ |
| 241 |
if (__sort_lt(*high, *low)) KSORT_SWAP(type_t, *low, *high); \ |
| 242 |
if (__sort_lt(*low, *mid)) KSORT_SWAP(type_t, *mid, *low); \ |
| 243 |
KSORT_SWAP(type_t, *mid, *(low+1)); \ |
| 244 |
ll = low + 1; hh = high; \ |
| 245 |
for (;;) { \ |
| 246 |
do ++ll; while (__sort_lt(*ll, *low)); \ |
| 247 |
do --hh; while (__sort_lt(*low, *hh)); \ |
| 248 |
if (hh < ll) break; \ |
| 249 |
KSORT_SWAP(type_t, *ll, *hh); \ |
| 250 |
} \ |
| 251 |
KSORT_SWAP(type_t, *low, *hh); \ |
| 252 |
if (hh <= k) low = ll; \ |
| 253 |
if (hh >= k) high = hh - 1; \ |
| 254 |
} \ |
| 255 |
} |
| 256 |
|
| 257 |
#define ks_mergesort(name, n, a, t) ks_mergesort_##name(n, a, t) |
| 258 |
#define ks_introsort(name, n, a) ks_introsort_##name(n, a) |
| 259 |
#define ks_combsort(name, n, a) ks_combsort_##name(n, a) |
| 260 |
#define ks_heapsort(name, n, a) ks_heapsort_##name(n, a) |
| 261 |
#define ks_heapmake(name, n, a) ks_heapmake_##name(n, a) |
| 262 |
#define ks_heapadjust(name, i, n, a) ks_heapadjust_##name(i, n, a) |
| 263 |
#define ks_ksmall(name, n, a, k) ks_ksmall_##name(n, a, k) |
| 264 |
|
| 265 |
#define ks_lt_generic(a, b) ((a) < (b)) |
| 266 |
#define ks_lt_str(a, b) (strcmp((a), (b)) < 0) |
| 267 |
|
| 268 |
typedef const char *ksstr_t; |
| 269 |
|
| 270 |
#define KSORT_INIT_GENERIC(type_t) KSORT_INIT(type_t, type_t, ks_lt_generic) |
| 271 |
#define KSORT_INIT_STR KSORT_INIT(str, ksstr_t, ks_lt_str) |
| 272 |
|
| 273 |
#endif |