include/libn/macro/qsort.h


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
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);                         \
        }                                          \
    }