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