pd.if.org Git - pdclib/blob - functions/stdlib/qsort.c

   1 /* ----------------------------------------------------------------------------
   2  * $Id$
   3  * ----------------------------------------------------------------------------
   4  * Public Domain C Library - http://pdclib.sourceforge.net
   5  * This code is Public Domain. Use, modify, and redistribute at will.
   6  * --------------------------------------------------------------------------*/
   7
   8 void qsort( void * base, size_t nelem, size_t size, int (*cmp) ( const void * e1, const void * e2) ) { /* TODO */ };
   9
  10 /* PDPC code - unreviewed
  11 /******************************************************************/
  12 /* qsort.c  --  Non-Recursive ISO C qsort() function              */
  13 /*                                                                */
  14 /* Public domain by Raymond Gardner, Englewood CO  February 1991  */
  15 /* Minor mods by Paul Edwards also public domain                  */
  16 /*                                                                */
  17 /* Usage:                                                         */
  18 /*     qsort(base, nbr_elements, width_bytes, compare_function);  */
  19 /*        void *base;                                             */
  20 /*        size_t nbr_elements, width_bytes;                       */
  21 /*        int (*compare_function)(const void *, const void *);    */
  22 /*                                                                */
  23 /* Sorts an array starting at base, of length nbr_elements, each  */
  24 /* element of size width_bytes, ordered via compare_function,     */
  25 /* which is called as  (*compare_function)(ptr_to_element1,       */
  26 /* ptr_to_element2) and returns < 0 if element1 < element2,       */
  27 /* 0 if element1 = element2, > 0 if element1 > element2.          */
  28 /* Most refinements are due to R. Sedgewick. See "Implementing    */
  29 /* Quicksort Programs", Comm. ACM, Oct. 1978, and Corrigendum,    */
  30 /* Comm. ACM, June 1979.                                          */
  31 /******************************************************************/
  32
  33 /* prototypes */
  34 static void swap_chars(char *, char *, size_t);
  35
  36 /*
  37 ** Compile with -DSWAP_INTS if your machine can access an int at an
  38 ** arbitrary location with reasonable efficiency.  (Some machines
  39 ** cannot access an int at an odd address at all, so be careful.)
  40 */
  41
  42 #ifdef   SWAP_INTS
  43  void swap_ints(char *, char *, size_t);
  44  #define  SWAP(a, b)  (swap_func((char *)(a), (char *)(b), width))
  45 #else
  46  #define  SWAP(a, b)  (swap_chars((char *)(a), (char *)(b), size))
  47 #endif
  48
  49 #define  COMP(a, b)  ((*comp)((void *)(a), (void *)(b)))
  50
  51 #define  T           7    /* subfiles of T or fewer elements will */
  52                           /* be sorted by a simple insertion sort */
  53                           /* Note!  T must be at least 3          */
  54
  55 void qsort(void *basep, size_t nelems, size_t size,
  56                             int (*comp)(const void *, const void *))
  57 {
  58    char *stack[40], **sp;       /* stack and stack pointer        */
  59    char *i, *j, *limit;         /* scan and limit pointers        */
  60    size_t thresh;               /* size of T elements in bytes    */
  61    char *base;                  /* base pointer as char *         */
  62
  63 #ifdef   SWAP_INTS
  64    size_t width;                /* width of array element         */
  65    void (*swap_func)(char *, char *, size_t); /* swap func pointer*/
  66
  67    width = size;                /* save size for swap routine     */
  68    swap_func = swap_chars;      /* choose swap function           */
  69    if ( size % sizeof(int) == 0 ) {   /* size is multiple of ints */
  70       width /= sizeof(int);           /* set width in ints        */
  71       swap_func = swap_ints;          /* use int swap function    */
  72    }
  73 #endif
  74
  75    base = (char *)basep;        /* set up char * base pointer     */
  76    thresh = T * size;           /* init threshold                 */
  77    sp = stack;                  /* init stack pointer             */
  78    limit = base + nelems * size;/* pointer past end of array      */
  79    for ( ;; ) {                 /* repeat until break...          */
  80       if ( limit - base > thresh ) {  /* if more than T elements  */
  81                                       /*   swap base with middle  */
  82          SWAP(((((size_t)(limit-base))/size)/2)*size+base, base);
  83          i = base + size;             /* i scans left to right    */
  84          j = limit - size;            /* j scans right to left    */
  85          if ( COMP(i, j) > 0 )        /* Sedgewick's              */
  86             SWAP(i, j);               /*    three-element sort    */
  87          if ( COMP(base, j) > 0 )     /*        sets things up    */
  88             SWAP(base, j);            /*            so that       */
  89          if ( COMP(i, base) > 0 )     /*      *i <= *base <= *j   */
  90             SWAP(i, base);            /* *base is pivot element   */
  91          for ( ;; ) {                 /* loop until break         */
  92             do                        /* move i right             */
  93                i += size;             /*        until *i >= pivot */
  94             while ( COMP(i, base) < 0 );
  95             do                        /* move j left              */
  96                j -= size;             /*        until *j <= pivot */
  97             while ( COMP(j, base) > 0 );
  98             if ( i > j )              /* if pointers crossed      */
  99                break;                 /*     break loop           */
 100             SWAP(i, j);       /* else swap elements, keep scanning*/
 101          }
 102          SWAP(base, j);         /* move pivot into correct place  */
 103          if ( j - base > limit - i ) {  /* if left subfile larger */
 104             sp[0] = base;             /* stack left subfile base  */
 105             sp[1] = j;                /*    and limit             */
 106             base = i;                 /* sort the right subfile   */
 107          } else {                     /* else right subfile larger*/
 108             sp[0] = i;                /* stack right subfile base */
 109             sp[1] = limit;            /*    and limit             */
 110             limit = j;                /* sort the left subfile    */
 111          }
 112          sp += 2;                     /* increment stack pointer  */
 113       } else {      /* else subfile is small, use insertion sort  */
 114          for ( j = base, i = j+size; i < limit; j = i, i += size )
 115             for ( ; COMP(j, j+size) > 0; j -= size ) {
 116                SWAP(j, j+size);
 117                if ( j == base )
 118                   break;
 119             }
 120          if ( sp != stack ) {         /* if any entries on stack  */
 121             sp -= 2;                  /* pop the base and limit   */
 122             base = sp[0];
 123             limit = sp[1];
 124          } else                       /* else stack empty, done   */
 125             break;
 126       }
 127    }
 128 }
 129
 130 /*
 131 **  swap nbytes between a and b
 132 */
 133
 134 static void swap_chars(char *a, char *b, size_t nbytes)
 135 {
 136    char tmp;
 137    do {
 138       tmp = *a; *a++ = *b; *b++ = tmp;
 139    } while ( --nbytes );
 140 }
 141
 142 #ifdef   SWAP_INTS
 143
 144 /*
 145 **  swap nints between a and b
 146 */
 147
 148 static void swap_ints(char *ap, char *bp, size_t nints)
 149 {
 150    int *a = (int *)ap, *b = (int *)bp;
 151    int tmp;
 152    do {
 153       tmp = *a; *a++ = *b; *b++ = tmp;
 154    } while ( --nints );
 155 }
 156
 157 #endif
 158 */