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 <string.h>
  10
  11 static inline size_t newgap(size_t gap)
  12 {
  13     gap = (gap * 10) / 13;
  14     if (gap == 9 || gap == 10)
  15         gap = 11;
  16
  17     if (gap < 1)
  18         gap = 1;
  19     return gap;
  20 }
  21
  22 void qsort(void *base, size_t nmemb, size_t size,
  23            int (*compar) (const void *, const void *))
  24 {
  25     size_t gap = nmemb;
  26     size_t i, j;
  27     char *p1, *p2;
  28     int swapped;
  29
  30     do {
  31         gap = newgap(gap);
  32         swapped = 0;
  33
  34         for (i = 0, p1 = base; i < nmemb - gap; i++, p1 += size) {
  35             j = i + gap;
  36             if (compar(p1, p2 = (char *)base + j * size) > 0) {
  37                 memswap(p1, p2, size);
  38                 swapped = 1;
  39             }
  40         }
  41     } while (gap > 1 || swapped);
  42 }