4 /** is only ever called for i1 < i2 */
5 typedef void (int i1, int i2, entity pass) swapfunc_t;
6 /** <0 for <, ==0 for ==, >0 for > (like strcmp) */
7 typedef int (int i1, int i2, entity pass) comparefunc_t;
9 void heapsort(int n, swapfunc_t swap, comparefunc_t cmp, entity pass)
11 #define heapify(_count) \
14 for (int start = floor(((_count) - 2) / 2); start >= 0; --start) \
16 siftdown(start, (_count) - 1); \
20 #define siftdown(_start, _end) \
23 for (int root = (_start); root * 2 + 1 <= (_end); ) \
25 int child = root * 2 + 1; \
26 if (child < (_end) && cmp(child, child + 1, pass) < 0) child += 1; \
27 if (cmp(root, child, pass) >= 0) break; \
28 swap(root, child, pass); \
43 void shuffle(float n, swapfunc_t swap, entity pass)
45 for (int i = 1; i < n; ++i)
47 // swap i-th item at a random position from 0 to i
48 // proof for even distribution:
51 // item n+1 gets at any position with chance 1/(n+1)
52 // all others will get their 1/n chance reduced by factor n/(n+1)
53 // to be on place n+1, their chance will be 1/(n+1)
54 // 1/n * n/(n+1) = 1/(n+1)
56 int j = floor(random() * (i + 1));
57 if (j != i) swap(j, i, pass);