diff options
| author | Nicholas Noll <nnoll523@gmail.com> | 2021-10-23 11:17:25 -0700 |
|---|---|---|
| committer | Nicholas Noll <nnoll523@gmail.com> | 2021-10-26 11:11:57 -0700 |
| commit | c8e1e71eb526475dd431443345262c2e5a627831 (patch) | |
| tree | ea9f7bcbba18a13f7ba8b32fcb1433ac2f4dd8b4 /include/libn/macro/qsort.h | |
| parent | 40f4c7305a041d4214df117491593898d04d0134 (diff) | |
chore(rename): libn -> base
Diffstat (limited to 'include/libn/macro/qsort.h')
| -rw-r--r-- | include/libn/macro/qsort.h | 91 |
1 files changed, 0 insertions, 91 deletions
diff --git a/include/libn/macro/qsort.h b/include/libn/macro/qsort.h deleted file mode 100644 index 6d0acaa..0000000 --- a/include/libn/macro/qsort.h +++ /dev/null @@ -1,91 +0,0 @@ -#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); \ - } \ - } |