home *** CD-ROM | disk | FTP | other *** search
/ Microsoft Programmer's Library 1.3 / Microsoft-Programers-Library-v1.3.iso / sampcode / alde_c / misc / util / qsortnet.c < prev    next >
Encoding:
Text File  |  1988-07-26  |  3.7 KB  |  193 lines
  1. Article 2718 (12 more) in net.sources:
  2. From: duane@anasazi.UUCP (Duane Morse)
  3. Subject: qsort source
  4. Message-ID: <276@anasazi.UUCP>
  5. Date: 29 Aug 85 14:04:07 GMT
  6. Date-Received: 2 Sep 85 06:12:20 GMT
  7. Distribution: net
  8. Organization: Anasazi, Phoenix Az.
  9. Lines: 182
  10.  
  11. --MORE--(14%)
  12. Here is my own version of qsort for those of you interested in sorting
  13. algorithms.
  14. --------------------SUBROUTINE FOLLOWS, THEN MY SIGNATURE -------------
  15. /*TITLE pqsort.c - quicksort algorithm 1/10/85 10:04:32 */
  16.  
  17. static char *version = "@(#)pqsort.c    1.1 1/10/85 10:04:32";
  18.  
  19. /*
  20. ** void pqsort(vec, nel, esize, compptr)
  21. **
  22. **  Quick Sort routine.
  23. **  Based on Knuth's ART OF COMPUTER PROGRAMMING, VOL III, pp 114-117.
  24. **  For some unknown reason, this works faster than the library's qsort.
  25. **
  26. ** Parameters:
  27. **  vec = points to beginning of structure to sort.
  28. **  nel = number of elements.
  29. **  esize = size of an element.
  30. **  compptr = points to the routine for comparing two elements.
  31. **
  32. ** Returns:
  33. **  Nothing.
  34. */
  35.  
  36. static int elsize;              /* Element size */
  37. static int (*comp)();           /* Address of comparison routing */
  38.  
  39. static void memexch(), mysort();
  40.  
  41. void pqsort(vec, nel, esize, compptr)
  42.  
  43. unsigned char *vec;
  44. int nel;
  45. int esize;
  46. int (*compptr)();
  47.  
  48. {
  49.   /* If less than 2 items, done */
  50.   if (nel < 2)
  51.     return;
  52.  
  53.   elsize = esize;
  54.   comp = compptr;
  55.  
  56.   /* Call the real worker */
  57.   mysort(vec, nel);
  58. }
  59. /*PAGE*/
  60. /*
  61. ** void mysort(vec, nel)
  62. **
  63. **  The real quick sort routine.
  64. **
  65. ** Parameters:
  66. **  vec = points to beginning of structure to sort.
  67. **  nel = number of elements.
  68. **
  69. **  esize = size of an element.
  70. **  compptr = points to the routine for comparing two elements.
  71. **
  72. ** Returns:
  73. **  Nothing.
  74. */
  75.  
  76. static void mysort(vec, nel)
  77.  
  78. unsigned char *vec;
  79. int nel;
  80.  
  81. {
  82.   register short i, j;
  83.   register unsigned char *iptr, *jptr, *kptr;
  84.  
  85.   /*
  86.   ** If 2 items, check them by hand.
  87.   */
  88.  
  89. begin:
  90.   if (nel == 2) {
  91.     if ((*comp)(vec, vec + elsize) > 0)
  92.       memexch(vec, vec + elsize, elsize);
  93.     return;
  94.   }
  95.  
  96.   /*
  97.   ** Initialize for this round.
  98.   */
  99.  
  100.   j = nel;
  101.   i = 0;
  102.   kptr = vec;
  103.   iptr = vec;
  104.   jptr = vec + elsize * nel;
  105. /*PAGE*/
  106.   while (--j > i) {
  107.  
  108.     /*
  109.     ** From the righthand side, find the first value that should be
  110.     ** to the left of k.
  111.     */
  112.  
  113.     jptr -= elsize;
  114.     if ((*comp)(jptr, kptr) > 0)
  115.       continue;
  116.  
  117.     /*
  118.     ** Now from the lefthand side, find the first value that should be
  119.     ** to the right of k.
  120.     */
  121.  
  122.     iptr += elsize;
  123.     while(++i < j && (*comp)(iptr, kptr) <= 0)
  124.       iptr += elsize;
  125.  
  126.     if (i >= j)
  127.       break;
  128.  
  129.     /*
  130.     ** Exchange the two items.
  131.     ** k will eventually end up between them.
  132.     */
  133.  
  134.     memexch(jptr, iptr, elsize);
  135.   }
  136.  
  137.   /*
  138.   ** Move item 0 into position.
  139.   */
  140.  
  141.   memexch(vec, iptr, elsize);
  142.  
  143.   /*
  144.   ** Now sort the two partitions.
  145.   */
  146.  
  147.   if ((nel -= (i + 1)) > 1)
  148.     mysort(iptr + elsize, nel);
  149.  
  150.   /*
  151.   ** To save a little time, just start the routine over by hand.
  152.   */
  153.  
  154.   if (i > 1) {
  155.     nel = i;
  156.     goto begin;
  157.   }
  158. }
  159. /*PAGE*/
  160. /*
  161. ** memexch(s1, s2, n)
  162. **
  163. **  Exchange the contents of two vectors.
  164. **
  165. ** Parameters:
  166. **  s1 = points to one vector.
  167. **  s2 = points to another vector.
  168. **  n = size of the vectors in bytes.
  169. **
  170. ** Returns:
  171. **  Nothing.
  172. */
  173.  
  174. static void memexch(s1, s2, n)
  175.  
  176. register unsigned char *s1;
  177. register unsigned char *s2;
  178. register int n;
  179.  
  180. {
  181.   register unsigned char c;
  182.  
  183.   while (n--) {
  184.     c = *s1;
  185.     *s1++ = *s2;
  186.     *s2++ = c;
  187.   }
  188. }
  189. ------------------------------------------------------
  190. -- 
  191.  
  192. Duane Morse     ...!noao!terak!anasazi!duane
  193. (602) 275-0302
  194.