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);
16 // siftdown(start, n - 1);
18 while (root * 2 + 1 <= n - 1) {
20 if (child < n - 1 && cmp(child, child + 1, pass) < 0) {
23 if (cmp(root, child, pass) < 0) {
24 swap(root, child, pass);
41 while (root * 2 + 1 <= end) {
43 if (child < end && cmp(child, child+1, pass) < 0) {
46 if (cmp(root, child, pass) < 0) {
47 swap(root, child, pass);
57 void shuffle(float n, swapfunc_t swap, entity pass)
59 for (int i = 1; i < n; ++i) {
60 // swap i-th item at a random position from 0 to i
61 // proof for even distribution:
64 // item n+1 gets at any position with chance 1/(n+1)
65 // all others will get their 1/n chance reduced by factor n/(n+1)
66 // to be on place n+1, their chance will be 1/(n+1)
67 // 1/n * n/(n+1) = 1/(n+1)
69 int j = floor(random() * (i + 1));