klibc/klibc/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, int (*compar)(const void *, const void *))
  23 {
  24   size_t gap = nmemb;
  25   size_t i, j;
  26   char *p1, *p2;
  27   int swapped;
  28
  29   do {
  30     gap = newgap(gap);
  31     swapped = 0;
  32
  33     for ( i = 0, p1 = base ; i < nmemb-gap ; i++, p1 += size ) {
  34       j = i+gap;
  35       if ( compar(p1, p2 = (char *)base+j*size) > 0 ) {
  36         memswap(p1, p2, size);
  37         swapped = 1;
  38       }
  39     }
  40   } while ( gap > 1 || swapped );
  41 }
  42