home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / comp / lang / c / 13381 < prev    next >
Encoding:
Text File  |  1992-09-09  |  4.1 KB  |  188 lines
  1. Newsgroups: comp.lang.c
  2. Path: sparky!uunet!usc!snorkelwacker.mit.edu!thunder.mcrcim.mcgill.edu!sobeco!ozrout!stirling
  3. From: stirling@ozrout.uucp (Stirling Westrup)
  4. Subject: Name this sort routine.
  5. Organization: Andre P. Ozrout
  6. Date: Wed, 09 Sep 1992 11:34:19 GMT
  7. Message-ID: <1992Sep09.113419.1131@ozrout.uucp>
  8. Summary: What is the name of this sort technique?
  9. Lines: 177
  10.  
  11.  
  12. I was recently working on a piece of code in which I was handed a linked
  13. list of objects, that was created in no particular order.  I had to process
  14. the individual links in ascending order, based on a key stored in the
  15. links.  I invented the following algorithm to apply a function to each link
  16. in the list, in order.  Now that I've tested it and it works, I've been 
  17. wondering what I should call it.  I assume (with a 86.7% probability) that
  18. it is a modification on one of the standard sort algorithms, but I'm darned
  19. if I recognize it.  I'm including a test program to illustrate how the
  20. algorithm works.
  21.  
  22. One final point, the following code does not seem to be too terribly fast,
  23. but the lists it will be handling are on the order of only about 50 entries
  24. anyway, so its no big deal.
  25.  
  26. (Hey, if it really is a new algorithm, I get to name it, right?  How
  27. about 'Stirling's Sort'?  Has a nice ring to it, doesn't it?)
  28.  
  29. -------------------------------8<---CUT HERE------>8----------------
  30. /* Does this sorting algorithm have a name? */
  31.  
  32. #include <stdio.h>
  33. #include <stdlib.h>
  34. #include <values.h>
  35.  
  36. #define NUM 100
  37. #define INT_MIN (MAXINT+1)      /* I wonder how portable this line is ... */
  38. #define INT_MAX (MAXINT)
  39.  
  40. #define new(T) malloc(sizeof(T))
  41. #define old(v) free(v)
  42.  
  43. typedef unsigned int Nat;
  44. typedef struct Lst Lst;
  45.  
  46. struct Lst
  47.   { int key;
  48.     Lst *prv;
  49.     Lst *nxt;
  50.   };
  51.  
  52.  
  53. /*
  54.   Add a new link to the front of the list
  55. */
  56. Lst* lst_add
  57.   ( Lst *lst,
  58.     int key
  59.   )
  60.   { Lst *tmp = new(Lst);
  61.  
  62.     if( tmp )
  63.       {
  64.     tmp->key = key;
  65.     tmp->prv = NULL;
  66.     tmp->nxt = lst;
  67.     if( lst )
  68.       lst->prv = tmp;
  69.       }
  70.     return tmp;
  71.   }
  72.  
  73. /*
  74.   Remove the indicated link from the List
  75. */
  76. Lst *lst_rmv
  77.   ( Lst *lst,
  78.     Lst *lnk
  79.   )
  80.   { Lst *ret;
  81.  
  82.     if( lnk->prv )
  83.       {
  84.     lnk->prv->nxt = lnk->nxt;
  85.     ret = lst;
  86.       }
  87.     else
  88.       ret = lnk->nxt;
  89.     if( lnk->nxt )
  90.       lnk->nxt->prv = lnk->prv;
  91.     old(lnk);
  92.     return ret;
  93.   }
  94.  
  95.  
  96.  
  97. /*
  98.   Apply the function <func> to the links of the list, in order by the
  99.   value of the link keys.
  100. */
  101. void lst_do_sorted
  102.   ( Lst *lst,
  103.     int kmin,
  104.     int kmax,
  105.     void (*func)
  106.       ( Lst *lnk,
  107.     void *arg
  108.       ),
  109.     void *arg
  110.   )
  111.   { int key;
  112.  
  113.     if( lst == NULL )
  114.       return;
  115.     key = lst->key;
  116.  
  117.     /*
  118.       if the key is not in the current interval, ignore it, but process
  119.       the rest of the list in the same interval
  120.     */
  121.     if( key < kmin || key > kmax )
  122.       {
  123.     lst_do_sorted(lst->nxt, kmin, kmax, func, arg );
  124.     return;
  125.       }
  126.  
  127.     /*
  128.       first apply the function to all of the lesser keys that exist
  129.       in the list
  130.     */
  131.     if( key > kmin )
  132.       lst_do_sorted(lst->nxt, kmin, key-1, func, arg );
  133.  
  134.     /*
  135.       Then apply the function to this link
  136.     */
  137.     func(lst,arg);
  138.  
  139.     /*
  140.       Finally apply the function to all other keys which are greater
  141.       or equal to this one.
  142.     */
  143.     lst_do_sorted(lst->nxt, key, kmax, func, arg );
  144.  
  145.     return;
  146.   }
  147.  
  148.  
  149. /*
  150.   The function to apply.  In this case, we merely print out the key.
  151. */
  152. void display
  153.   ( Lst *lnk,
  154.     void *arg
  155.   )
  156.   {
  157.     printf("%6d  ",lnk->key);
  158.   }
  159.  
  160.  
  161. int main
  162.   ( int argc,
  163.     char *argv[]
  164.   )
  165.   { Nat i;
  166.     Lst *lst = NULL;
  167.     Lst *tmp;
  168.  
  169.     srand(999);
  170.     for( i = 0 ; i < NUM; i++ )
  171.       lst = lst_add(lst,rand());
  172.     printf("Unsorted List:\n");
  173.     for( tmp = lst; tmp; tmp = tmp->nxt )
  174.       /* don't you wish x ->= y worked? */
  175.       printf("%6d  ",tmp->key);
  176.     printf("\nDisplayed in sorted order:\n");
  177.     lst_do_sorted(lst, INT_MIN, INT_MAX, display, NULL );
  178.     printf("\n");
  179.     for( i = 0 ; i < NUM; i++ )
  180.       lst = lst_rmv(lst,lst);
  181.     return 0;
  182.   }
  183. -- 
  184. ||    BUNGEE SIDEWAYS!                              o   )))
  185. ||                                                 /-- ///
  186. |P~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\_  \\\      __ -_
  187. ||    stirling@ozrout.uucp                                 ((( (_)T(_)
  188.