qcsrc/lib/sort.qh

   1 #ifndef SORT_H
   2 #define SORT_H
   3
   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;
   8
   9 void heapsort(int n, swapfunc_t swap, comparefunc_t cmp, entity pass)
  10 {
  11         #define heapify(_count) \
  12                 do \
  13                 { \
  14                         for (int start = floor(((_count) - 2) / 2); start >= 0; --start) \
  15                         { \
  16                                 siftdown(start, (_count) - 1); \
  17                         } \
  18                 } \
  19                 while (0)
  20
  21         #define siftdown(_start, _end) \
  22                 do \
  23                 { \
  24                         for (int root = (_start); root * 2 + 1 <= (_end); ) \
  25                         { \
  26                                 int child = root * 2 + 1; \
  27                                 if (child < (_end) && cmp(child, child + 1, pass) < 0) child += 1; \
  28                                 if (cmp(root, child, pass) >= 0) break; \
  29                                 swap(root, child, pass); \
  30                                 root = child; \
  31                         } \
  32                 } \
  33                 while (0)
  34
  35         heapify(n);
  36         int end = n - 1;
  37         while (end > 0)
  38         {
  39                 swap(0, end, pass);
  40                 end -= 1;
  41                 siftdown(0, end);
  42         }
  43 }
  44
  45 void shuffle(float n, swapfunc_t swap, entity pass)
  46 {
  47         for (int i = 1; i < n; ++i)
  48         {
  49                 // swap i-th item at a random position from 0 to i
  50                 // proof for even distribution:
  51                 //   n = 1: obvious
  52                 //   n -> n+1:
  53                 //     item n+1 gets at any position with chance 1/(n+1)
  54                 //     all others will get their 1/n chance reduced by factor n/(n+1)
  55                 //     to be on place n+1, their chance will be 1/(n+1)
  56                 //     1/n * n/(n+1) = 1/(n+1)
  57                 //     q.e.d.
  58                 int j = floor(random() * (i + 1));
  59                 if (j != i) swap(j, i, pass);
  60         }
  61 }
  62
  63 #endif