com32/lib/qsort.c

   1 /*
   2  * qsort.c
   3  *
   4  * This is actually combsort.  It's an O(n log n) algorithm with
   5  * simplicity/small code size being its main virtue.
   6  */
   7
   8 #include <stddef.h>
   9 #include <stdlib.h>
  10 #include <string.h>
  11
  12 static inline size_t newgap(size_t gap)
  13 {
  14     gap = (gap * 10) / 13;
  15     if (gap == 9 || gap == 10)
  16         gap = 11;
  17
  18     if (gap < 1)
  19         gap = 1;
  20     return gap;
  21 }
  22
  23 void qsort(void *base, size_t nmemb, size_t size,
  24            int (*compar) (const void *, const void *))
  25 {
  26     size_t gap = nmemb;
  27     size_t i, j;
  28     char *p1, *p2;
  29     int swapped;
  30
  31     if (!nmemb)
  32         return;
  33
  34     do {
  35         gap = newgap(gap);
  36         swapped = 0;
  37
  38         for (i = 0, p1 = base; i < nmemb - gap; i++, p1 += size) {
  39             j = i + gap;
  40             if (compar(p1, p2 = (char *)base + j * size) > 0) {
  41                 memswap(p1, p2, size);
  42                 swapped = 1;
  43             }
  44         }
  45     } while (gap > 1 || swapped);
  46 }