diff options
Diffstat (limited to 'include/base/macro/qsort.h')
| -rw-r--r-- | include/base/macro/qsort.h | 91 |
1 files changed, 91 insertions, 0 deletions
diff --git a/include/base/macro/qsort.h b/include/base/macro/qsort.h new file mode 100644 index 0000000..6d0acaa --- /dev/null +++ b/include/base/macro/qsort.h @@ -0,0 +1,91 @@ +#pragma once + +/* + * Nicholas Noll (2020) + * Straight implementation of Sedgewick's median qsort + * #ref: "Implementing Quicksort Programs" (1978) + * + * @LEN: name of parameter length + * @QLESS: name of function that computes array[i] < array[j] + * should return a boolean + * @QSWAP: name of function that swaps array[i] <-> array[j] + * this could swap multiple arrays + * + * NOTE: This can perform on strided arrays. + * Make sure to use parens liberally to ensure hygeine! + */ + +#define QSORT(LEN, QLESS, QSWAP) \ + int i, j, m, r, l; \ + struct { \ + int i, j; \ + } *sp, base[48]; \ + sp = base; \ + \ + l = 1; \ + r = LEN-1; \ + \ + if (LEN <= 14) goto ENDOUTER; \ +OUTERLOOP: \ + SWAP((l+r)/2, l+1); \ + \ + if (QLESS(r, l+1)) QSWAP(r, l+1); \ + if (QLESS(r, l)) QSWAP(r, l); \ + if (QLESS(l, l+1)) QSWAP(l, l+1); \ + \ + i = l+1; \ + j = r; \ + \ +INNERLOOP: \ + do ++i; while(QLESS(i, l)); \ + do --j; while(QLESS(l, j)); \ + if (j < i) goto ENDINNER; \ + QSWAP(i, j); \ + goto INNERLOOP; \ + \ +ENDINNER: \ + QSWAP(l, j); \ + \ + if (MAX(j-l, r-i+1) <= 14) { \ + if (sp == base) { \ + goto ENDOUTER; \ + } else { \ + l = sp[-1].i; \ + r = sp[-1].j; \ + sp--; \ + } \ + } else { \ + if (MIN(j-l, r-i+1) <= 14) { \ + if (j-l > r-i+1) { \ + l = l; \ + r = j-1; \ + } else { \ + l = i; \ + r = r; \ + } \ + } else { \ + if (j-l > r-i+1) { \ + sp->i = l; \ + sp->j = j-1; \ + sp++; \ + \ + l = i; \ + r = r; \ + } else { \ + sp->i = i; \ + sp->j = r; \ + sp++; \ + \ + l = l; \ + r = j-1; \ + } \ + } \ + } \ + goto OUTERLOOP; \ + \ +ENDOUTER: \ + for (i = 1; i < LEN; i++) { \ + for (j = i; j > 0 && QLESS(j, j-1); j--) { \ + QSWAP(j, j-1); \ + } \ + } |