4 /** is only ever called for i1 < i2 */
5 typedef void (float i1, float i2, entity pass) swapfunc_t;
6 /** <0 for <, ==0 for ==, >0 for > (like strcmp) */
7 typedef float (float i1, float i2, entity pass) comparefunc_t;
9 void heapsort(float n, swapfunc_t swap, comparefunc_t cmp, entity pass)
14 int start = floor((n - 2) / 2);
17 // siftdown(start, n - 1);
19 while (root * 2 + 1 <= n - 1)
22 if (child < n - 1 && cmp(child, child + 1, pass) < 0) child += 1;
23 if (cmp(root, child, pass) < 0)
25 swap(root, child, pass);
45 while (root * 2 + 1 <= end)
48 if (child < end && cmp(child, child + 1, pass) < 0) child += 1;
49 if (cmp(root, child, pass) < 0)
51 swap(root, child, pass);
63 void shuffle(float n, swapfunc_t swap, entity pass)
65 for (int i = 1; i < n; ++i)
67 // swap i-th item at a random position from 0 to i
68 // proof for even distribution:
71 // item n+1 gets at any position with chance 1/(n+1)
72 // all others will get their 1/n chance reduced by factor n/(n+1)
73 // to be on place n+1, their chance will be 1/(n+1)
74 // 1/n * n/(n+1) = 1/(n+1)
76 int j = floor(random() * (i + 1));
77 if (j != i) swap(j, i, pass);