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         {
  17                 // siftdown(start, n - 1);
  18                 root = start;
  19                 while (root * 2 + 1 <= n - 1)
  20                 {
  21                         child = root * 2 + 1;
  22                         if (child < n - 1 && cmp(child, child + 1, pass) < 0) child += 1;
  23                         if (cmp(root, child, pass) < 0)
  24                         {
  25                                 swap(root, child, pass);
  26                                 root = child;
  27                         }
  28                         else
  29                         {
  30                                 break;
  31                         }
  32                 }
  33                 // end of siftdown
  34                 --start;
  35         }
  36
  37         // extract
  38         int end = n - 1;
  39         while (end > 0)
  40         {
  41                 swap(0, end, pass);
  42                 end -= 1;
  43                 // siftdown(0, end);
  44                 root = 0;
  45                 while (root * 2 + 1 <= end)
  46                 {
  47                         child = root * 2 + 1;
  48                         if (child < end && cmp(child, child + 1, pass) < 0) child += 1;
  49                         if (cmp(root, child, pass) < 0)
  50                         {
  51                                 swap(root, child, pass);
  52                                 root = child;
  53                         }
  54                         else
  55                         {
  56                                 break;
  57                         }
  58                 }
  59                 // end of siftdown
  60         }
  61 }
  62
  63 void shuffle(float n, swapfunc_t swap, entity pass)
  64 {
  65         for (int i = 1; i < n; ++i)
  66         {
  67                 // swap i-th item at a random position from 0 to i
  68                 // proof for even distribution:
  69                 //   n = 1: obvious
  70                 //   n -> n+1:
  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)
  75                 //     q.e.d.
  76                 int j = floor(random() * (i + 1));
  77                 if (j != i) swap(j, i, pass);
  78         }
  79 }
  80
  81 #endif