src/sort.c

   1 #include "angband.h"
   2 #include "sort.h"
   3
   4
   5 /*
   6  * Angband sorting algorithm -- quick sort in place
   7  *
   8  * Note that the details of the data we are sorting is hidden,
   9  * and we rely on the "ang_sort_comp()" and "ang_sort_swap()"
  10  * function hooks to interact with the data, which is given as
  11  * two pointers, and which may have any user-defined form.
  12  */
  13 void ang_sort_aux(vptr u, vptr v, int p, int q)
  14 {
  15         int z, a, b;
  16
  17         /* Done sort */
  18         if (p >= q) return;
  19
  20         /* Pivot */
  21         z = p;
  22
  23         /* Begin */
  24         a = p;
  25         b = q;
  26
  27         /* Partition */
  28         while (TRUE)
  29         {
  30                 /* Slide i2 */
  31                 while (!(*ang_sort_comp)(u, v, b, z)) b--;
  32
  33                 /* Slide i1 */
  34                 while (!(*ang_sort_comp)(u, v, z, a)) a++;
  35
  36                 /* Done partition */
  37                 if (a >= b) break;
  38
  39                 /* Swap */
  40                 (*ang_sort_swap)(u, v, a, b);
  41
  42                 /* Advance */
  43                 a++, b--;
  44         }
  45
  46         /* Recurse left side */
  47         ang_sort_aux(u, v, p, b);
  48
  49         /* Recurse right side */
  50         ang_sort_aux(u, v, b + 1, q);
  51 }
  52
  53
  54 /*
  55  * Angband sorting algorithm -- quick sort in place
  56  *
  57  * Note that the details of the data we are sorting is hidden,
  58  * and we rely on the "ang_sort_comp()" and "ang_sort_swap()"
  59  * function hooks to interact with the data, which is given as
  60  * two pointers, and which may have any user-defined form.
  61  */
  62 void ang_sort(vptr u, vptr v, int n)
  63 {
  64         /* Sort the array */
  65         ang_sort_aux(u, v, 0, n - 1);
  66 }
  67
  68
  69