home *** CD-ROM | disk | FTP | other *** search
/ SPACE 2 / SPACE - Library 2 - Volume 1.iso / program / 316 / libsrc / pqsort.c < prev    next >
Encoding:
C/C++ Source or Header  |  1988-10-20  |  3.1 KB  |  177 lines
  1. /*TITLE pqsort.c - quicksort algorithm 1/10/85 10:04:32 */
  2.  
  3. static char *version = "@(#)pqsort.c    1.1 1/10/85 10:04:32";
  4.  
  5. /*
  6. ** void pqsort(vec, nel, esize, compptr)
  7. **
  8. **  Quick Sort routine.
  9. **  Based on Knuth's ART OF COMPUTER PROGRAMMING, VOL III, pp 114-117.
  10. **  For some unknown reason, this works faster than the library's qsort.
  11. **
  12. ** Parameters:
  13. **  vec = points to beginning of structure to sort.
  14. **  nel = number of elements.
  15. **  esize = size of an element.
  16. **  compptr = points to the routine for comparing two elements.
  17. **
  18. ** Returns:
  19. **  Nothing.
  20. */
  21.  
  22. static int elsize;        /* Element size */
  23. static int (*comp)();        /* Address of comparison routing */
  24.  
  25. static void memexch(), mysort();
  26.  
  27. void pqsort(vec, nel, esize, compptr)
  28.  
  29. unsigned char *vec;
  30. int nel;
  31. int esize;
  32. int (*compptr)();
  33.  
  34. {
  35.   /* If less than 2 items, done */
  36.   if (nel < 2)
  37.     return;
  38.  
  39.   elsize = esize;
  40.   comp = compptr;
  41.  
  42.   /* Call the real worker */
  43.   mysort(vec, nel);
  44. }
  45.  
  46.  
  47. /*PAGE*/
  48. /*
  49. ** void mysort(vec, nel)
  50. **
  51. **  The real quick sort routine.
  52. **
  53. ** Parameters:
  54. **  vec = points to beginning of structure to sort.
  55. **  nel = number of elements.
  56. **
  57. **  esize = size of an element.
  58. **  compptr = points to the routine for comparing two elements.
  59. **
  60. ** Returns:
  61. **  Nothing.
  62. */
  63.  
  64. static void mysort(vec, nel)
  65.  
  66. unsigned char *vec;
  67. int nel;
  68.  
  69. {
  70.   register short i, j;
  71.   register unsigned char *iptr, *jptr, *kptr;
  72.  
  73.   /*
  74.   ** If 2 items, check them by hand.
  75.   */
  76.  
  77. begin:
  78.   if (nel == 2) {
  79.     if ((*comp)(vec, vec + elsize) > 0)
  80.       memexch(vec, vec + elsize, elsize);
  81.     return;
  82.   }
  83.  
  84.   /*
  85.   ** Initialize for this round.
  86.   */
  87.  
  88.   j = nel;
  89.   i = 0;
  90.   kptr = vec;
  91.   iptr = vec;
  92.   jptr = vec + elsize * nel;
  93. /*PAGE*/
  94.   while (--j > i) {
  95.  
  96.     /*
  97.     ** From the righthand side, find the first value that should be
  98.     ** to the left of k.
  99.     */
  100.  
  101.     jptr -= elsize;
  102.     if ((*comp)(jptr, kptr) > 0)
  103.       continue;
  104.  
  105.     /*
  106.     ** Now from the lefthand side, find the first value that should be
  107.     ** to the right of k.
  108.     */
  109.  
  110.     iptr += elsize;
  111.     while(++i < j && (*comp)(iptr, kptr) <= 0)
  112.       iptr += elsize;
  113.  
  114.     if (i >= j)
  115.       break;
  116.  
  117.     /*
  118.     ** Exchange the two items.
  119.     ** k will eventually end up between them.
  120.     */
  121.  
  122.     memexch(jptr, iptr, elsize);
  123.   }
  124.  
  125.   /*
  126.   ** Move item 0 into position.
  127.   */
  128.  
  129.   memexch(vec, iptr, elsize);
  130.  
  131.   /*
  132.   ** Now sort the two partitions.
  133.   */
  134.  
  135.   if ((nel -= (i + 1)) > 1)
  136.     mysort(iptr + elsize, nel);
  137.  
  138.   /*
  139.   ** To save a little time, just start the routine over by hand.
  140.   */
  141.  
  142.   if (i > 1) {
  143.     nel = i;
  144.     goto begin;
  145.   }
  146. }
  147. /*PAGE*/
  148. /*
  149. ** memexch(s1, s2, n)
  150. **
  151. **  Exchange the contents of two vectors.
  152. **
  153. ** Parameters:
  154. **  s1 = points to one vector.
  155. **  s2 = points to another vector.
  156. **  n = size of the vectors in bytes.
  157. **
  158. ** Returns:
  159. **  Nothing.
  160. */
  161.  
  162. static void memexch(s1, s2, n)
  163.  
  164. register unsigned char *s1;
  165. register unsigned char *s2;
  166. register int n;
  167.  
  168. {
  169.   register unsigned char c;
  170.  
  171.   while (n--) {
  172.     c = *s1;
  173.     *s1++ = *s2;
  174.     *s2++ = c;
  175.   }
  176. }
  177.