qcsrc/lib/sort.qh

   1 #ifndef SORT_H
   2 #define SORT_H
   3
   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;
   8
   9 void heapsort(float n, swapfunc_t swap, comparefunc_t cmp, entity pass)
  10 {
  11     int root, child;
  12
  13     // heapify
  14     int start = floor((n - 2) / 2);
  15     while (start >= 0) {
  16         // siftdown(start, n - 1);
  17         root = start;
  18         while (root * 2 + 1 <= n - 1) {
  19             child = root * 2 + 1;
  20             if (child < n - 1 && cmp(child, child + 1, pass) < 0) {
  21                 child += 1;
  22             }
  23             if (cmp(root, child, pass) < 0) {
  24                 swap(root, child, pass);
  25                 root = child;
  26             } else {
  27                 break;
  28             }
  29         }
  30         // end of siftdown
  31         --start;
  32     }
  33
  34     // extract
  35     int end = n - 1;
  36     while (end > 0) {
  37         swap(0, end, pass);
  38         end -= 1;
  39         // siftdown(0, end);
  40         root = 0;
  41         while (root * 2 + 1 <= end) {
  42             child = root * 2 + 1;
  43             if (child < end && cmp(child, child+1, pass) < 0) {
  44                 child += 1;
  45             }
  46             if (cmp(root, child, pass) < 0) {
  47                 swap(root, child, pass);
  48                 root = child;
  49             } else {
  50                 break;
  51             }
  52         }
  53         // end of siftdown
  54     }
  55 }
  56
  57 void shuffle(float n, swapfunc_t swap, entity pass)
  58 {
  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:
  62         //   n = 1: obvious
  63         //   n -> n+1:
  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)
  68         //     q.e.d.
  69         int j = floor(random() * (i + 1));
  70         if (j != i)
  71             swap(j, i, pass);
  72     }
  73 }
  74
  75 #endif