src/util/tag-sorter.c

   1 #include "util/tag-sorter.h"
   2
   3 /*
   4  * Exchange two sort-entries
   5  * (should probably be coded inline
   6  * for speed increase)
   7  */
   8 static void swap(tag_type *a, tag_type *b)
   9 {
  10     tag_type temp;
  11
  12     temp = *a;
  13     *a = *b;
  14     *b = temp;
  15 }
  16
  17 /*
  18  * Insertion-Sort algorithm
  19  * (used by the Quicksort algorithm)
  20  */
  21 static void insertion_sort(tag_type elements[], int number)
  22 {
  23     tag_type tmp;
  24     for (int i = 1; i < number; i++) {
  25         tmp = elements[i];
  26         int j;
  27         for (j = i; (j > 0) && (elements[j - 1].tag > tmp.tag); j--)
  28             elements[j] = elements[j - 1];
  29         elements[j] = tmp;
  30     }
  31 }
  32
  33 /*
  34  * Helper function for Quicksort
  35  */
  36 static tag_type median3(tag_type elements[], int left, int right)
  37 {
  38     int center = (left + right) / 2;
  39
  40     if (elements[left].tag > elements[center].tag)
  41         swap(&elements[left], &elements[center]);
  42     if (elements[left].tag > elements[right].tag)
  43         swap(&elements[left], &elements[right]);
  44     if (elements[center].tag > elements[right].tag)
  45         swap(&elements[center], &elements[right]);
  46
  47     swap(&elements[center], &elements[right - 1]);
  48     return (elements[right - 1]);
  49 }
  50
  51 /*
  52  * Quicksort algorithm
  53  *
  54  * The "median of three" pivot selection eliminates
  55  * the bad case of already sorted input.
  56  *
  57  * We use insertion_sort for smaller sub-arrays,
  58  * because it is faster in this case.
  59  *
  60  * For details see: "Data Structures and Algorithm
  61  * Analysis in C" by Mark Allen Weiss.
  62  */
  63 static void quicksort(tag_type elements[], int left, int right)
  64 {
  65     tag_type pivot;
  66     const int array_size_cutoff = 4;
  67     if (left + array_size_cutoff <= right) {
  68         pivot = median3(elements, left, right);
  69
  70         int i = left;
  71         int j = right - 1;
  72
  73         while (TRUE) {
  74             while (elements[++i].tag < pivot.tag)
  75                 ;
  76             while (elements[--j].tag > pivot.tag)
  77                 ;
  78
  79             if (i < j)
  80                 swap(&elements[i], &elements[j]);
  81             else
  82                 break;
  83         }
  84
  85         swap(&elements[i], &elements[right - 1]);
  86
  87         quicksort(elements, left, i - 1);
  88         quicksort(elements, i + 1, right);
  89     } else {
  90         insertion_sort(elements + left, right - left + 1);
  91     }
  92 }
  93
  94 /*
  95  * Frontend for the sorting algorithm
  96  *
  97  * Sorts an array of tagged pointers
  98  * with <number> elements.
  99  */
 100 void tag_sort(tag_type elements[], int number) { quicksort(elements, 0, number - 1); }