qcsrc/lib/sort.qh

   1 #pragma once
   2
   3 /** is only ever called for i1 < i2 */
   4 USING(swapfunc_t, void(int i1, int i2, entity pass));
   5 /** <0 for <, ==0 for ==, >0 for > (like strcmp) */
   6 USING(comparefunc_t, int(int i1, int i2, entity pass));
   7
   8 ERASEABLE
   9 void heapsort(int n, swapfunc_t swap, comparefunc_t cmp, entity pass)
  10 {
  11 #define heapify(_count) \
  12         MACRO_BEGIN \
  13                 for (int start = floor(((_count) - 2) / 2); start >= 0; --start) { \
  14                         siftdown(start, (_count) - 1); \
  15                 } \
  16         MACRO_END
  17
  18 #define siftdown(_start, _end) \
  19         MACRO_BEGIN \
  20                 for (int root = (_start); root * 2 + 1 <= (_end); ) { \
  21                         int child = root * 2 + 1; \
  22                         if (child < (_end) && cmp(child, child + 1, pass) < 0) { child += 1; } \
  23                         if (cmp(root, child, pass) >= 0) { break; } \
  24                         swap(root, child, pass); \
  25                         root = child; \
  26                 } \
  27         MACRO_END
  28
  29         heapify(n);
  30         int end = n - 1;
  31         while (end > 0) {
  32                 swap(0, end, pass);
  33                 end -= 1;
  34                 siftdown(0, end);
  35         }
  36 }
  37
  38 ERASEABLE
  39 void shuffle(float n, swapfunc_t swap, entity pass)
  40 {
  41         for (int i = 1; i < n; ++i) {
  42                 // swap i-th item at a random position from 0 to i
  43                 // proof for even distribution:
  44                 //   n = 1: obvious
  45                 //   n -> n+1:
  46                 //     item n+1 gets at any position with chance 1/(n+1)
  47                 //     all others will get their 1/n chance reduced by factor n/(n+1)
  48                 //     to be on place n+1, their chance will be 1/(n+1)
  49                 //     1/n * n/(n+1) = 1/(n+1)
  50                 //     q.e.d.
  51                 int j = floor(random() * (i + 1));
  52                 if (j != i) { swap(j, i, pass); }
  53         }
  54 }