home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1992 March / Source_Code_CD-ROM_Walnut_Creek_March_1992.iso / usenet / altsrcs / 1 / 1716 < prev    next >
Encoding:
Text File  |  1990-12-28  |  3.1 KB  |  120 lines
  1. Newsgroups: alt.sources
  2. From: chris@mimsy.umd.edu (Chris Torek)
  3. Subject: [comp.lang.c] Re: Sorting Algorithm
  4. Message-ID: <1990Aug25.222150.11265@math.lsa.umich.edu>
  5. Date: Sat, 25 Aug 90 22:21:50 GMT
  6.  
  7. Archive-name: torek-lsort/25-Aug-90
  8. Original-posting-by: chris@mimsy.umd.edu (Chris Torek)
  9. Original-subject: Re: Sorting Algorithm
  10. Reposted-by: emv@math.lsa.umich.edu (Edward Vielmetti)
  11.  
  12. [Reposted from comp.lang.c.
  13. Comments on this service to emv@math.lsa.umich.edu (Edward Vielmetti).]
  14.  
  15. Just for fun, here is yet another linked list sort.  This attempts to
  16. use the fewest instructions possible for those n-squared loops :-)
  17.  
  18. #include <stddef.h>
  19.  
  20. /*
  21.  * Sort a linked list in which the `next' pointer is the first entry.
  22.  * A pointer to the (new) list head is returned.
  23.  *
  24.  * lsort() performs a binary merge sort.  The length parameter is
  25.  * optional; if 0, lsort runs a first pass over the list to find the
  26.  * length.
  27.  */
  28. struct list {            /* pseudo */
  29.     struct list *next;
  30. };
  31.  
  32. void *
  33. lsort(list, listlen, compare)
  34.     void *list;
  35.     int listlen;
  36.     register int (*compare)();
  37. {
  38.     struct list *hd;
  39.     register struct list *p, **xp, *a, *b;
  40.     register int i, left, mergelen;
  41.     register struct list **ea, **eb;
  42.  
  43.     hd = list;
  44.     if (listlen == 0) {
  45.         for (i = 0, p = hd; p; p = p->next)
  46.             i++;
  47.         listlen = i;
  48.     }
  49.  
  50.     /* if list is empty, this loop does not run */
  51.     for (mergelen = 1; mergelen < listlen; mergelen <<= 1) {
  52.         /*
  53.          * Merge ceil(listlen/mergelen) lists, pairwise.
  54.          *
  55.          * On each trip through the loop below, we split the
  56.          * list headed by p into two sublists a and b of length
  57.          * mergelen or less, followed by a trailing part p.
  58.          * List a will always be complete, but list b may be
  59.          * short when we near the tail.  (It can even be empty;
  60.          * we handle this as a special case for speed reasons.)
  61.          * We then merge lists a and b, sticking each next
  62.          * element at *xp and tracking xp along.  Eventually
  63.          * either a or b runs out; we can then tack on what
  64.          * remains of the other.
  65.          */
  66.         left = listlen;
  67.         p = hd;
  68.         xp = &hd;
  69.         do {
  70.             /*
  71.              * Make list a, length mergelen, and figure
  72.              * out how many are left after that.  If none
  73.              * or negative, list b will be empty; stop.
  74.              */
  75.             i = mergelen;
  76.             if ((left -= i) <= 0) {
  77.                 *xp = p;
  78.                 break;
  79.             }
  80.             for (a = p; --i > 0; p = p->next)
  81.                 /* void */;
  82.             ea = &p->next, p = p->next, *ea = NULL;
  83.  
  84.             /* make list b, length min(mergelen,left) */
  85.             i = mergelen;
  86.             if ((left -= i) < 0)
  87.                 i += left;
  88.             for (b = p; --i > 0; p = p->next)
  89.                 /* void */;
  90.             eb = &p->next, p = p->next, *eb = NULL;
  91.  
  92.             /* tail in p, empty iff left<=0 */
  93.             for (;;) {
  94.                 /* append from appropriate sublist */
  95.                 if ((*compare)((void *)a, (void *)b) <= 0) {
  96.                     *xp = a;
  97.                     xp = &a->next;
  98.                     if ((a = a->next) == NULL) {
  99.                         *xp = b;
  100.                         xp = eb;
  101.                         break;
  102.                     }
  103.                 } else {
  104.                     *xp = b;
  105.                     xp = &b->next;
  106.                     if ((b = b->next) == NULL) {
  107.                         *xp = a;
  108.                         xp = ea;
  109.                         break;
  110.                     }
  111.                 }
  112.             }
  113.         } while (left > 0);
  114.     }
  115.     return ((void *)hd);
  116. }
  117. -- 
  118. In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 405 2750)
  119. Domain:    chris@cs.umd.edu    Path:    uunet!mimsy!chris
  120.