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