libs/basekit/source/Sorting.c

   1 #include "Sorting.h"
   2
   3 typedef struct
   4 {
   5         void *context;
   6         SDSortCompareCallback *comp;
   7         SDSortSwapCallback *swap;
   8 } SDSort;
   9
  10 int Sorting_isSorted(SDSort *self, size_t size);
  11 void Sorting_quickSort(SDSort *self, size_t lb, size_t ub);
  12 int Sorting_quickSortRearrange(SDSort *self, size_t lb, size_t ub);
  13
  14 void Sorting_context_comp_swap_size_type_(void *context,
  15                                                                         SDSortCompareCallback *comp,
  16                                                                         SDSortSwapCallback *swap,
  17                                                                         size_t size,
  18                                                                         SDSortType type)
  19 {
  20         SDSort q;
  21         SDSort *self = &q;
  22
  23         self->context = context;
  24         self->comp = comp;
  25         self->swap = swap;
  26
  27         switch (type)
  28         {
  29                 case SDQuickSort:
  30                         if (!Sorting_isSorted(self, size)) Sorting_quickSort(self, 0, size-1);
  31                         break;
  32         }
  33 }
  34
  35 int Sorting_isSorted(SDSort *self, size_t size)
  36 {
  37         SDSortCompareCallback *comp = self->comp;
  38         void *context = self->context;
  39         size_t i;
  40
  41         for (i = 0; i + 1 < size; i ++)
  42         {
  43                 if ((*comp)(context, i, i + 1) > 0)
  44                 {
  45                         return 0;
  46                 }
  47         }
  48
  49         return 1;
  50 }
  51
  52 void Sorting_quickSort(SDSort *self, size_t lb, size_t ub)
  53 {
  54         if (lb < ub)
  55         {
  56                 int j = Sorting_quickSortRearrange(self, lb, ub);
  57
  58                 if (j)
  59                 {
  60                         Sorting_quickSort(self, lb, j - 1);
  61                 }
  62
  63                 Sorting_quickSort(self, j + 1, ub);
  64         }
  65 }
  66
  67 int Sorting_quickSortRearrange(SDSort *self, size_t lb, size_t ub)
  68 {
  69         SDSortCompareCallback *comp = self->comp;
  70         SDSortSwapCallback *swap = self->swap;
  71         void *context = self->context;
  72
  73         do {
  74                 while (ub > lb && (*comp)(context, ub, lb) >= 0)
  75                 {
  76                         ub --;
  77                 }
  78
  79                 if (ub != lb)
  80                 {
  81                         (*swap)(context, ub, lb);
  82
  83                         while (lb < ub && (*comp)(context, lb, ub) <= 0)
  84                         {
  85                                 lb ++;
  86                         }
  87
  88                         if (lb != ub)
  89                         {
  90                                 (*swap)(context, lb, ub);
  91                         }
  92                 }
  93         } while (lb != ub);
  94
  95         return lb;
  96 }