home *** CD-ROM | disk | FTP | other *** search
/ Monster Media 1994 #1 / monster.zip / monster / PROG_C / SNIP9404.ZIP / LL_QSORT.C < prev    next >
C/C++ Source or Header  |  1994-04-03  |  4KB  |  147 lines
  1. /*========== SNIP SNIP SNIP ==========*/
  2. /* SORT.H */
  3.  
  4. void    *sortl(void *list, void *(*getnext)(void *), 
  5.                 void (*setnext)(void *, void *), 
  6.                 int (*compare)(void *, void *));
  7.  
  8. /*========== SNIP SNIP SNIP ==========*/
  9. /* SORT.C */
  10. #include    <stdlib.h>
  11. #include    "sort.h"
  12.  
  13.  
  14. /*
  15.     This is a quicksort routine to be used to sort linked-lists
  16.     by Jon Guthrie.
  17. */
  18.  
  19. void    *sortl(list, getnext, setnext, compare)
  20. void    *list, *(*getnext)(void *), (*setnext)(void *, void *);
  21. int     (*compare)(void *, void *);
  22.  
  23. {
  24. void    *low_list, *high_list, *current, *pivot, *temp;
  25. int     result;
  26.  
  27.     /*
  28.         Test for empty list.
  29.     */
  30.     if(NULL == list)
  31.         return(NULL);
  32.  
  33.     /*
  34.         Find the first element that doesn't have the same value as the first
  35.         element.
  36.     */
  37.     current = list;
  38.     do
  39.     {
  40.         current = getnext(current);
  41.         if(NULL == current)
  42.             return(list);
  43.     }   while(0 == (result = compare(list, current)));
  44.  
  45.     /*
  46.         My pivot value is the lower of the two.  This insures that the sort
  47.         will always terminate by guaranteeing that there will be at least one
  48.         member of both of the sublists.
  49.     */
  50.     if(result > 0)
  51.         pivot = current;
  52.     else
  53.         pivot = list;
  54.  
  55.     /* Initialize the sublist pointers */
  56.     low_list = high_list = NULL;
  57.  
  58.     /*
  59.         Now, separate the items into the two sublists
  60.     */
  61.     current = list;
  62.     while(NULL != current)
  63.     {
  64.         temp = getnext(current);
  65.         if(compare(pivot, current) < 0)
  66.         {
  67.             /* add one to the high list */
  68.             setnext(current, high_list);
  69.             high_list = current;
  70.         }
  71.         else
  72.         {
  73.             /* add one to the low list */
  74.             setnext(current, low_list);
  75.             low_list = current;
  76.         }
  77.         current = temp;
  78.     }
  79.  
  80.     /*
  81.         And, recursively call the sort for each of the two sublists.
  82.     */
  83.     low_list  = sortl(low_list, getnext, setnext, compare);
  84.     high_list = sortl(high_list, getnext, setnext, compare);
  85.  
  86.     /*
  87.         Now, I have to put the "high" list after the end of the "low" list.  
  88.         To do that, I first have to find the end of the "low" list...
  89.     */
  90.     current = temp = low_list;
  91.     while(1)
  92.     {
  93.         current = getnext(current);
  94.         if(NULL == current)
  95.             break;
  96.         temp = current;
  97.     }
  98.  
  99.     /*
  100.         Then, I put the "high" list at the end of the low list
  101.     */
  102.     setnext(temp, high_list);
  103.     return(low_list);
  104. }
  105.  
  106. /* mergesort linked lists by Ray Gardner */
  107. /* split list into 2 parts, sort each recursively, merge */
  108. void    *sortl(p, getnext, setnext, compare)
  109. void    *p, *(*getnext)(void *), (*setnext)(void *, void *);
  110. int     (*compare)(void *, void *);
  111. {
  112.    void *q, *r, *head;
  113.  
  114.    if ( p ) {                           /* first split it */
  115.       r = p;
  116.       for ( q = getnext(r); q && (q = getnext(q)) != NULL; q = getnext(q) )
  117.          r = getnext(r);
  118.       q = getnext(r);
  119.       setnext(r, NULL);
  120.       if ( q ) {                        /* now sort each sublist */
  121.          p = sortl(p, getnext, setnext, compare);
  122.          q = sortl(q, getnext, setnext, compare);
  123.          if ( compare(q, p) < 0 ) {     /* smallest item becomes list head */
  124.             head = q;
  125.             q = getnext(q);
  126.          } else {
  127.             head = p;
  128.             p = getnext(p);
  129.          }
  130.          for ( r = head; p && q; ) {    /* now merge the lists under head */
  131.             if ( keycmp(q, p) < 0 ) {
  132.                setnext(r, q);
  133.                r = q;
  134.                q = getnext(q);
  135.             } else {
  136.                setnext(r, p);
  137.                r = p;
  138.                p = getnext(p);
  139.             }
  140.          }
  141.          setnext(r, (p ? p : q));       /* append the leftovers */
  142.          p = head;
  143.       }
  144.    }
  145.    return p;
  146. }
  147.