home *** CD-ROM | disk | FTP | other *** search
/ Atari FTP / ATARI_FTP_0693.zip / ATARI_FTP_0693 / Mint / mntlib25.zoo / qsort.c < prev    next >
C/C++ Source or Header  |  1992-09-05  |  8KB  |  293 lines
  1. /*
  2.  * qsort - parts adapted from Doug Schmidt's sort challenge posting
  3.  *       thanks Doug
  4.  *
  5.  *        ++jrb    bammi@dsrgsun.ces.cwru.edu
  6.  */
  7.  
  8. #if (defined(minix) || defined(unix))
  9. #  include <sys/types.h>
  10. #  if defined(sparc) && !defined(__GNUC__)
  11. #    include <alloca.h>
  12. #  endif
  13. #  ifdef minix    /* minix 1.5 note: size_t as defined in stdlib is not */
  14.         /* used for obvious reasons */
  15. #    include "lib.h"
  16. #  endif
  17. #else
  18. #  include <stddef.h>
  19. #  include <stdlib.h>
  20. #endif
  21. #include <string.h>
  22. #include <memory.h>
  23.  
  24. #ifdef __GNUC__
  25. #  ifdef minix
  26.      void *alloca(unsigned long);
  27.      typedef unsigned long size_t;
  28. #  endif
  29. #  define INLINE inline
  30. #else
  31. #  define INLINE /* */
  32. #endif
  33. #ifndef _COMPILER_H
  34. #include <compiler.h>
  35. #endif
  36.  
  37. /* macros for incrementing/decrementing void pointers */
  38. #define INC(v, size) v = (void *)(((char *)v) + size)
  39. #define DEC(v, size) v = (void *)(((char *)v) - size)
  40.  
  41.     /* the next 4 #defines implement a very fast in-line stack abstraction */
  42.     
  43. #define MAKE_STACK(S) \
  44.     ((stack_node *) alloca((size_t)(sizeof(stack_node) * (S))))
  45. #define PUSH(LOW,HIGH) \
  46.     top->lo = LOW; top->hi = HIGH; top++
  47. #define POP(LOW,HIGH) \
  48.     --top; LOW = top->lo; HIGH = top->hi
  49. #define STACK_NOT_EMPTY \
  50.     (stack < top)                
  51.  
  52. INLINE static void swap __PROTO((unsigned char *, unsigned char *, size_t));
  53. INLINE static void Move __PROTO((unsigned char *, unsigned char *, size_t));
  54. INLINE static void insert_sort __PROTO((void *, void *, size_t, int (*)(const void *, const void *)));
  55. INLINE static void *find_pivot __PROTO((void *, void *, size_t, int (*)(const void *, const void *)));
  56.  
  57. /* Discontinue quicksort algorithm when partition gets below this size. */
  58.  
  59. #ifndef MAX_THRESH
  60. #define MAX_THRESH 15
  61. #endif
  62.  
  63. /* Data structure for stack of unfulfilled obligations. */
  64. typedef struct 
  65. {
  66.     void *lo;
  67.     void *hi;
  68. } stack_node;
  69.  
  70. static void *scratch;    /* scratch mem */
  71.  
  72. /* swap two elements of size n each */
  73. INLINE static void swap(a, b, n)
  74. unsigned char *a, *b;
  75. size_t n;
  76. {
  77.     unsigned char t;
  78.     while(n--)
  79.     {
  80.     t    = *a;
  81.         *a++ = *b;
  82.     *b++ = t;
  83.     }
  84. }
  85.  
  86.  
  87. /* move src to dest */
  88. INLINE static void Move(src, dst, n)
  89. unsigned char *src, *dst;
  90. size_t n;
  91. {
  92.     while(n--)
  93.     *dst++ = *src++;
  94. }
  95.  
  96.  
  97. /* Once main array is partially sorted by quicksort the remainder is 
  98.    completely sorted using insertion sort, since this is efficient 
  99.    for partitions below MAX_THRESH size. BASE points to the beginning 
  100.    of the array to sort, and END_PTR points at the very last element in
  101.    the array (*not* one beyond it!). */
  102.  
  103. INLINE static void 
  104. #if __STDC__
  105.     insert_sort(void *base, void *end_ptr, size_t siz, int (*cmp)(const void *,
  106.                                   const void *))
  107. #else
  108.     insert_sort(base, end_ptr, siz, cmp)
  109.     void *base, *end_ptr;
  110.     size_t siz;
  111.     int (*cmp)();
  112. #endif
  113. {
  114.     void *run_ptr;
  115.     void *tmp_ptr = end_ptr;
  116.     void *temp = scratch;
  117.  
  118.     /* Find the largest element in the array and put it at the 
  119.        end of the array.  This acts like a sentinel, and it speeds
  120.        up the inner loop of insertion sort. */
  121.  
  122.     for (run_ptr = (void *)((char *)end_ptr - siz); run_ptr >= base;
  123.      DEC(run_ptr, siz))
  124.     if ((*cmp)(run_ptr, tmp_ptr) > 0) 
  125.         tmp_ptr = run_ptr;
  126.  
  127.     if(tmp_ptr != end_ptr)
  128.     { swap (tmp_ptr, end_ptr, siz); }
  129.  
  130.     /* Typical insertion sort, but we run from the `right-hand-side'
  131.        downto the `left-hand-side.' */
  132.     
  133.     for (run_ptr = (void *)((char *)end_ptr - siz); run_ptr > base;
  134.      DEC(run_ptr, siz))
  135.     {
  136.     tmp_ptr = (void *)((char *)run_ptr - siz);
  137.     Move(tmp_ptr, temp, siz);
  138.  
  139.     /* Select the correct location for the new element, 
  140.        by sliding everyone down by 1 to make room! */
  141.     
  142. #if 0
  143.     while ((*cmp)(temp , ((char *)tmp_ptr += siz)) > 0)
  144. #else
  145.     while (((INC(tmp_ptr, siz)), (*cmp)(temp, tmp_ptr)) > 0)
  146. #endif
  147.         Move(tmp_ptr, ((unsigned char *)tmp_ptr - siz), siz);
  148.  
  149.     Move(temp, (unsigned char *)tmp_ptr - siz, siz);
  150.     }
  151. }
  152.  
  153. /* Return the median value selected from among the 
  154.    LOW, MIDDLE, and HIGH.  Rearrange LOW and HIGH so
  155.    the three values are sorted amongst themselves. 
  156.    This speeds up later work... */
  157.  
  158. INLINE static void *
  159. #if __STDC__
  160.     find_pivot(void *low, void *high, size_t siz, int (*cmp)(const void *,
  161.                                  const void *))
  162. #else
  163.     find_pivot(low, high, siz, cmp)
  164.     void *low, *high;
  165.     size_t siz;
  166.     int (*cmp)();
  167. #endif
  168. {
  169.     void *middle = (void *) ((char *)low + ((((char *)high - (char *)low)/siz) >> 1) * siz);
  170.     
  171.     if ((*cmp)(middle, low) < 0)
  172.     { swap (middle, low, siz); }
  173.     if ((*cmp)(high, middle) < 0)
  174.     { swap (middle, high, siz); }
  175.     else 
  176.     return middle;
  177.     
  178.     if ((*cmp)(middle, low)  < 0)
  179.     { swap (middle, low, siz); }
  180.     
  181.     return middle;
  182. }
  183.  
  184. /* Order elements using quicksort.  This implementation incorporates
  185.    4 optimizations discussed in Sedgewick:
  186.    
  187.    1. Non-recursive, using an explicit stack of log (n) pointers that 
  188.    indicate the next array partition to sort.
  189.    
  190.    2. Choses the pivot element to be the median-of-three, reducing
  191.    the probability of selecting a bad pivot value.
  192.    
  193.    3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving
  194.    insertion sort to sort within the partitions.  This is a
  195.    big win, since insertion sort is faster for small, mostly
  196.    sorted array segements.
  197.    
  198.    4. The larger of the 2 sub-partitions are always pushed onto the
  199.    stack first, with the algorithm then concentrating on the
  200.    smaller partition.  This *guarantees* no more than log (n)
  201.    stack size is needed! */
  202.  
  203. void qsort(base, total_elems, size, cmp)
  204. void *base;
  205. size_t total_elems;
  206. size_t size;
  207. int (*cmp) __PROTO((const void *, const void *));
  208. {
  209.     if (total_elems > 1)
  210.     {
  211.     void        *lo;
  212.     void        *hi;
  213.     void        *left_ptr;
  214.     void        *right_ptr;
  215.     void        *pivot;
  216.     size_t        Thresh = MAX_THRESH * size;
  217.     stack_node  *stack;
  218.     stack_node  *top;  
  219.     size_t max_stack_size = 1;
  220.  
  221.     /* Calculate the exact stack space required in the worst case.
  222.        This is approximately equal to the log base 2 of TOTAL_ELEMS. */
  223.     
  224.     {   size_t i;    /* this helps the compiler */
  225.         for (i = 1; i < total_elems; i += i) 
  226.             max_stack_size++;
  227.     }
  228.     /* Create the stack, or die trying! */
  229.     if ((stack = MAKE_STACK (max_stack_size)) != NULL)
  230.         top = stack;
  231.     else
  232.         return;
  233.  
  234.     /* allocate scratch */
  235.     if((scratch = (void *)alloca(size)) == (void *)0)
  236.         return;    /* die */
  237.     
  238.     lo = base;
  239.     hi = (void *) ((char *)lo + (total_elems - 1) * size);
  240.  
  241.     do {
  242.         next: if((char *)hi <= ((char *)lo + Thresh)) /* correct unsigned comapare */
  243.         {
  244.         insert_sort(lo, hi, size, cmp);
  245.         if(STACK_NOT_EMPTY)
  246.             {  POP(lo, hi); goto next; }
  247.         else
  248.             break;
  249.         }
  250.         /* otherwise next iteration of qsort */
  251.         /* Select the median-of-three here. This allows us to
  252.            skip forward for the LEFT_PTR and RIGHT_PTR. */
  253.         pivot = find_pivot (lo, hi, size, cmp);
  254.         left_ptr  = (void *)((char *)lo + size);
  255.         right_ptr = (void *)((char *)hi - size); 
  256.  
  257.         /* Here's the famous ``collapse the walls'' section of
  258.            quicksort.  Gotta like those tight inner loops! */
  259.         do { /* partition loop */  /* see knuth for <= */
  260.         while ((left_ptr < hi) && ((*cmp)(left_ptr, pivot) <= 0))
  261.             INC(left_ptr, size);
  262.         
  263.         while ((right_ptr > lo) && ((*cmp)(pivot, right_ptr) <= 0))
  264.             DEC(right_ptr, size);
  265.         
  266.         if (left_ptr < right_ptr) 
  267.                 {
  268.             swap (left_ptr, right_ptr, size);
  269.             INC(left_ptr,  size);
  270.             DEC(right_ptr, size);
  271.                 }
  272.         else if (left_ptr == right_ptr) 
  273.                 {
  274.             INC(left_ptr, size); 
  275.             DEC(right_ptr, size); 
  276.             break;
  277.                 }
  278.             } while (left_ptr <= right_ptr);
  279.         
  280.         if (((char *)right_ptr - (char *)lo) > ((char *)hi - (char *)left_ptr)) 
  281.             {                   /* push larger left table */
  282.         PUSH (lo, right_ptr);
  283.         lo = left_ptr;
  284.             }
  285.         else 
  286.             {                   /* push larger right table */
  287.         PUSH (left_ptr, hi);
  288.         hi = right_ptr;
  289.             }
  290.         } while(1);    /* when stack is empty it'll break out */
  291.     } /* if total_elems > 1 */
  292. }
  293.